Cod sursa(job #256692)

Utilizator StigmaSimina Pitur Stigma Data 12 februarie 2009 00:03:53
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.26 kb
#include <stdio.h>
#include <math.h>

struct punct{double x,y;};

punct v[120000];
long n,h,sol[120000];


long poz2(long li, long ls)
{long i0=0,j0=-1,aux;
punct a;

 while (li<ls)
 {if ((v[ls].x-v[1].x)*(v[li].y-v[1].y)<(v[li].x-v[1].x)*(v[ls].y-v[1].y))
  {a=v[li];
   v[li]=v[ls];
   v[ls]=a;
   aux=-j0;
   j0=-i0;
   i0=aux;
  }
  li+=i0;
  ls+=j0;
 }
return li;
}



void sort2(long li, long ls)
{long k;
if (li<ls)
 {k=poz2(li,ls);
  sort2(li,k-1);
  sort2(k+1,ls);
 }
}




int verif(punct p2, punct p1, punct p0)
{return (p2.x*p1.y+p1.x*p0.y+p0.x*p2.y-p0.x*p1.y-p2.x*p0.y-p1.x*p2.y<0);
}


int main()
{long i,j;
punct aux;

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

 scanf("%l", &n);

  scanf("%lf %lf", &v[1].x,&v[1].y);
  j=1;

  for (i=2;i<=n;i++)
   {scanf("%lf %lf", &v[i].x,&v[i].y);
    if (v[i].x<v[j].x || (v[i].x==v[j].x && v[i].y<v[j].y))
     j=i;
   }

 aux=v[j];
 v[j]=v[1];
 v[1]=aux;


sort2(2,n);

sol[1]=1;
sol[2]=2;
h=2;

for (i=3;i<=n;i++)
 {for (;!verif(v[sol[h-1]],v[sol[h]],v[sol[i]]) && h>2;h--);
  h++;
  sol[h]=i;
  }


printf("%l\n",h);
for (i=1;i<=h;i++)
 printf("%lf %lf\n", v[sol[i]].x, v[sol[i]].y);

return 0;
}