Cod sursa(job #288675)

Utilizator firewizardLucian Dobre firewizard Data 25 martie 2009 23:45:27
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.06 kb
#include <stdio.h>
#include <algorithm>
using namespace std;
struct pcte{double x;double y;};
pcte p[120005],P,aux;
pcte stack[120005];
int i,j,k,l,m,n,c,q=3;
int isLeft(pcte p1,pcte p2,pcte p)
{
       return ((double)(p1.x*p.y+p.x*p2.y+p2.x*p1.y)>
               (double)(p2.x*p.y+p2.y*p1.x+p.x*p1.y));
}
int comp(const pcte &x,const pcte &y)
{
    return isLeft(y,x,P);
}
int main()
{
    freopen ("infasuratoare.in","r",stdin);
    freopen ("infasuratoare.out","w",stdout);
    scanf("%d",&n);
    for (i=1;i<=n;++i)
        scanf("%lf %lf",&p[i].x,&p[i].y);
    P.x=1000000001;P.y=1000000001;
    for (i=1;i<=n;++i)
        if (p[i].x<P.x||(p[i].x==P.x&&p[i].y<P.y))
           P.x=p[i].x,P.y=p[i].y,c=i;
    aux=p[c];p[c]=p[n];p[n]=aux;
    sort(p+1,p+n,comp);
    stack[1]=P;
    stack[2]=p[1];
    for (i=2;i<=n;++i){
        while (!isLeft(stack[q-2],p[i],stack[q-1]))q--;
        stack[q++]=p[i];
        }
    q--;
    printf("%d\n",q-1);
    for (i=2;i<=q;++i)
        printf("%lf %lf\n",stack[i].x,stack[i].y);
    return 0;
}