Cod sursa(job #765464)

Utilizator BlaugranasEnal Gemaledin Blaugranas Data 7 iulie 2012 19:47:55
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.18 kb
#include<cstdio>
#include<algorithm>
using namespace std;
#define N 120001
struct P
{double x,y;};
int n,i,g,w,u,v,j,t,l;
P d[N],c[N],e[N],b[N];
double k;

int A(P a,P b)
{return a.x<b.x||(a.x==b.x&&a.y<b.y);}

double S(P a,P b,P p)
{return (b.x-a.x)*(p.y-a.y)-(p.x-a.x)*(b.y-a.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",&d[i].x,&d[i].y);
sort(d+1,d+n+1,A);
v=u=g=1,w=n,c[1]=e[1]=d[g];
for(i=2;i<n;i++)
      {k=S(d[g],d[w],d[i]);
      if(k<0)
             {c[++u]=d[i];
             while(u>2&&S(c[u-2],c[u],c[u-1])>0)
                   c[u-1]=c[u--];}
      else
             if(k>0)
                   {e[++v]=d[i];
                   while(v>2&&S(e[v-2],e[v],e[v-1])<0)
                          e[v-1]=e[v--];}}
e[++v]=c[++u]=d[w],t=v,l=u;
while(t>2)
if(S(e[t-2],e[t],e[t-1])<0)
      e[t-1]=e[v--];
else
      t--;
while(l>2)
if(S(c[l-2],c[l],c[l-1])>0)
      c[l-1]=c[u--];
else
      l--;
printf("%d\n",v+u-2);
for(i=1;i<=u;i++)
      printf("%lf %lf\n",c[i].x,c[i].y);
for(j=v-1;j>1;j--)
      printf("%lf %lf\n",e[j].x,e[j].y);
return 0;}