Cod sursa(job #291163)

Utilizator ConsstantinTabacu Raul Consstantin Data 29 martie 2009 14:31:41
Problema Infasuratoare convexa Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 1.04 kb
#include<stdio.h>
#include<algorithm>
using namespace std;

struct punct {double x,y;}v[12010];

int i,j,n,k,l,p=1,sol[12010];

int sign (int i,int j,int k)
{
double x,y;
x=(v[i].x-v[k].x)*(v[j].y-v[k].y);
y=(v[j].x-v[k].x)*(v[i].y-v[k].y);
return (x-y>0);

}

struct cmp
{
        bool operator()(const punct &a,const punct &b)const
        {return (double)(a.x-v[1].x)*(b.y-v[1].y)>(double)(b.x-v[1].x)*(a.y-v[1].y);
        }
};

int main(){

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


scanf("%d",&n);

for(i=1;i<=n;i++)
        {scanf("%lf %lf",&v[i].x,&v[i].y);
        if(v[i].x<v[p].x)p=i;
        else
        if(v[i].x==v[p].x&&v[i].y<v[p].y)p=i;
        }
punct aux;
aux=v[p];
v[p]=v[1];
v[1]=aux;

sort(v+2,v+n+1,cmp());
k=1;
sol[1]=1;
for(i=2;i<=n;i++)
        {while(k>=2&&sign(sol[k-1],sol[k],i)<1)k--;
        k++;
        sol[k]=i;

        }

printf("%d\n",k);
for(i=1;i<=k;i++)
        printf("%0.4lf %0.4lf\n",v[sol[i]].x,v[sol[i]].y);
return 0;}