Cod sursa(job #1242899)

Utilizator rzvrzvNicolescu Razvan rzvrzv Data 15 octombrie 2014 10:23:20
Problema Infasuratoare convexa Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 1.35 kb
#include<cstdio>
#include<algorithm>

using namespace std;

pair <double,double> v[130000];
int i,s[130000],h,k,q,n;
double x,y;
bool ok[130000];

int semn(pair <int,int> a,pair<double,double> b,pair<double,double> c)
{
    double x,y,z;
    x=a.second-b.second;
    y=b.first-a.first;
    z=a.first*b.second-b.first*a.second;
    x*=c.first;
    y*=c.second;
    x=x+y+z;
    if(x+1e-12<0)
    {
        return -1;
    }
    if(x+1e-12>0)
    {
        return 1;
    }
    if(x+1e-12==0)
    {
        return 0;
    }
}

int main()
{
    freopen("infasuratoare.in","r",stdin);
    freopen("infasuratoare.out","w",stdout);
    scanf("%d",&n);
    for(i=1;i<=n;i++)
    {
        scanf("%lf%lf",&x,&y);
        v[i]=make_pair(x,y);
    }
    sort(v+1,v+n+1);
    ok[2]=true;
    s[1]=1;
    s[2]=2;
    i=3;
    q=1;
    k=2;
    while(ok[1]==false)
    {
        while(ok[i]==true)
        {
            if(i==n)
            {
                q=-1;
            }
            i+=q;
        }
        while(k>=2&&semn(v[s[k-1]],v[s[k]],v[i])==-1)
        {
            ok[s[k]]=false;;
            k--;
        }
        s[++k]=i;
        ok[i]=true;
    }
    h=k-1;
    printf("%d\n",h);
    for(i=2;i<=h+1;i++)
    {
        printf("%.6lf %.6lf\n",v[s[i]].first,v[s[i]].second);
    }
    return 0;
}