Cod sursa(job #393511)

Utilizator freak93Adrian Budau freak93 Data 9 februarie 2010 16:24:57
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.38 kb
#include<cstdio>
#include<cstring>
#include<algorithm>
#define x first
#define y second

using namespace std;

const char iname[]="infasuratoare.in";
const char oname[]="infasuratoare.out";
const int maxn=120000;

int n,i,j,s[maxn],been[maxn],step,k;

pair<double,double> P[maxn];
double eps=1e-12;

int cmp(double x,double y)
{
    if(x+eps<y)
        return -1;
    if(y+eps<x)
        return 1;
    return 0;
}

bool operator<(pair<double,double> a,pair<double,double> b)
{
    int d=cmp(a.x,b.x);
    if(d)
        return d==-1;
    return cmp(a.y,b.y)==-1;
}

double area(pair<double,double> a,pair<double,double> b,pair<double,double> c)
{
    return a.x*b.y-a.y*b.x+b.x*c.y-b.y*c.x+c.x*a.y-c.y*a.x;
}

int main()
{
    freopen(iname,"r",stdin);
    freopen(oname,"w",stdout);

    scanf("%d",&n);
    for(i=0;i<n;++i)
        scanf("%lf %lf",&P[i].x,&P[i].y);

    sort(P,P+n);
    s[0]=0;
    s[1]=1;
    been[1]=1;
    step=1;
    k=1;
    i=step;
    while(been[0]==0)
    {
        if(i==n-1)
            step=-1;
        while(been[i])
            i+=step;
        while(k&&cmp(area(P[s[k-1]],P[s[k]],P[i]),0)<=0)
            been[s[k--]]=0;
        been[s[++k]=i]=1;
    }

    printf("%d\n",k);
    for(i=1;i<=k;++i)
        printf("%.6lf %.6lf\n",P[s[i]].x,P[s[i]].y);

    fclose(stdin);
    fclose(stdout);

    return 0;
}