Cod sursa(job #606400)

Utilizator BlaugranasEnal Gemaledin Blaugranas Data 4 august 2011 10:05:14
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.35 kb
#include<fstream.h>
#define N 120001
typedef struct po
{double x,y;};
long n,i,g,w,u,v,j,t,l;
po d[N],c[N],e[N],b[N];
double k;
void me(po a[N],long p,long q)
{long m=(p+q)/2,i,j,k;
if(p==q)
      return;
me(a,p,m),me(a,m+1,q);
for(i=p,j=m+1,k=p;i<=m||j<=q;)
if(j>q||(i<=m&&(a[i].x<a[j].x||(a[i].x==a[j].x&&a[i].y<a[j].y))))
      b[k++]=a[i++];
else
      b[k++]=a[j++];
for(i=p;i<=q;i++)
      a[i]=b[i];}

double s(po a,po b,po p)
{return (b.x-a.x)*(p.y-a.y)-(p.x-a.x)*(b.y-a.y);}
int main()
{ifstream f("infasuratoare.in");
freopen("infasuratoare.out","w",stdout);
f>>n;
for(i=1;i<=n;i++)
      f>>d[i].x>>d[i].y;
me(d,1,n);
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("%ld\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;}