Cod sursa(job #2921312)

Utilizator alexdumitruAlexandru Dumitru alexdumitru Data 30 august 2022 09:08:44
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.42 kb
#include <bits/stdc++.h>


using namespace std;

const int NMAX=120005;

pair<double,double> a[NMAX];

int n,i,j;

vector<int> hull;

int st[NMAX];

bool vis[NMAX];

const double EPS = 1e-12;

double det(pair<double,double> o, pair<double,double> a, pair<double,double> b)
{
    return (a.first-o.first)*(b.second-o.second)-(a.second-o.second)*(b.first-o.first);
}

void solve()
{
    cin>>n;
    for(i=1;i<=n;i++)
        cin>>a[i].first>>a[i].second;
    sort(a+1,a+n+1);
    st[1]=1;st[2]=st[0]=2;
    vis[2]=1;
    for(i=1;i<=n;i++)
    {
        if(vis[i])continue;
        while(st[0]>=2&&det(a[st[st[0]-1]],a[st[st[0]]],a[i])<EPS)
            vis[st[st[0]--]]=0;
        st[++st[0]]=i;
        vis[i]=1;
    }
    for(i=n-1;i>0;i--)
    {
        if(vis[i])continue;
        while(st[0]>=2&&det(a[st[st[0]-1]],a[st[st[0]]],a[i])<EPS)
            vis[st[st[0]--]]=0;
        st[++st[0]]=i;
        vis[i]=1;
    }
    cout<<--st[0]<<'\n';;
    while(st[0]>0)
        hull.push_back(st[st[0]--]);
    reverse(hull.begin(),hull.end());
    cout<<fixed<<setprecision(6);
    hull.push_back(hull[0]);
    for(i=1;i<hull.size();i++)
        cout<<a[hull[i]].first<<' '<<a[hull[i]].second<<'\n';
}

signed main()
{
    freopen("infasuratoare.in","r",stdin);
    freopen("infasuratoare.out","w",stdout);
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    solve();
    return 0;
}