Cod sursa(job #291123)

Utilizator ConsstantinTabacu Raul Consstantin Data 29 martie 2009 13:53:17
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.1 kb
#include<stdio.h>
#include<algorithm>
using namespace std;

struct punct {float x,y,tg;}sigur,v[12010],c[12010];

int i,j,k,l,m,n;
int arie(double a,double b,double d,double e,double g,double h)
{return (a*e+b*g+d*h)-(g*e+h*a+d*b);

}
int cmp(punct a,punct b){
return a.tg>b.tg;
}
int main(){

freopen("infasuratoare.in","r",stdin);
freopen("infasuratoare.out","w",stdout);

scanf("%d",&n);
sigur.x=sigur.y=(float (1))/(float(0));
for(i=1;i<=n;i++)
        {scanf("%f %f",&v[i].x,&v[i].y);
        if(v[i].x<sigur.x)sigur=v[i];
        else
        if(v[i].x==sigur.x&&v[i].y<sigur.y)sigur=v[i];
        }


k=0;
for(i=1;i<=n;i++)
        if(v[i].x!=sigur.x||v[i].y!=sigur.y)
                {k++;
                v[k]=v[i];
                v[k].tg=(v[i].y-sigur.y)/(v[i].x-sigur.x);}

sort(v+1,v+n,cmp);
n=n-1;
c[1]=sigur;
c[2]=v[1];
k=2;
for(i=2;i<=n;i++)
        {while(arie(c[k-1].x,c[k-1].y,c[k].x,c[k].y,v[i].x,v[i].y)>0&&k>=2)k--;
        k++;
        c[k]=v[i];
        }

printf("%d\n",k);
for(i=1;i<=k;i++)
printf("%0.4f %0.4f\n",c[i].x,c[i].y);


return 0;}