Cod sursa(job #1999584)

Utilizator mihneacazCazacu Mihnea mihneacaz Data 11 iulie 2017 16:21:42
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.78 kb
#include<cstdio>
#include<fstream>
#include<algorithm>
#include<vector>
#define NMAX 120005
using namespace std;
pair <double,double> v[NMAX];
int sol[NMAX],st[NMAX];
bool viz[NMAX];
double det(pair <double,double> a,pair <double,double> b,pair <double,double> c)
{
    return a.first*b.second+b.first*c.second+c.first*a.second-b.second*c.first-c.second*a.first-a.second*b.first;
}
int main()
{
    ifstream cin("infasuratoare.in");
    ofstream cout("infasuratoare.out");
    int n;
    cin>>n;
    for(int i=1; i<=n; ++i)
    {
        double a,b;
        cin>>a>>b;
        v[i].first=a;
        v[i].second=b;
    }
    sort(v+1,v+n+1);
    int top=0,a,b;
    for(int i=1; i<=n; ++i)
    {
        if(top>1)
        {
            while(top>1 && det(v[a],v[b],v[i])>0)
            {
                viz[st[top]]=0;
                --top;
                a=st[top-1];
                b=st[top];
            }
        }
        st[++top]=i;
        viz[st[top]]=1;
        a=st[top-1];
        b=st[top];
    }
    int rez=0;
    for(int i=1; i<=top; ++i)
        sol[++rez]=st[i];
    top=1;
    st[top]=n;
    for(int i=n; i>=1; --i)
    {
        if(!viz[i] || i==1)
        {
                 if(top>1)
        {
            while(top>1 && det(v[a],v[b],v[i])>0)
            {
                viz[st[top]]=0;
                --top;
                a=st[top-1];
                b=st[top];
            }
        }
        st[++top]=i;
        viz[st[top]]=1;
        a=st[top-1];
        b=st[top];
        }
    }
    for(int i=2; i<top; ++i)
        sol[++rez]=st[i];
    cout<<rez<<'\n';
    for(int i=rez; i>=1; --i)
    {
        cout.precision(6);
        cout<<fixed<<v[sol[i]].first<<" "<<v[sol[i]].second<<'\n';
    }
    return 0;
}