Cod sursa(job #256713)

Utilizator StigmaSimina Pitur Stigma Data 12 februarie 2009 02:15:43
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.99 kb
#include <stdio.h>
#include <math.h>
#include <stdio.h>
#include <values.h>

struct punct{double x,y,c;};

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



double dist(punct a, punct b)
{double aux;
aux=sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
return aux;
}




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

 while (li<ls)
 {if ((double)(v[ls].x-v[1].x)*(v[li].y-v[1].y)<(double)(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);
 }
}





/*long poz1(long li, long ls)
{int i0=0,j0=-1,aux;
punct a;

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



void sort1(long li, long ls)
{long k;
if (li<ls)
 {k=poz1(li,ls);
  sort1(li,k-1);
  sort1(k+1,ls);
 }
}                           */











int verif(punct p2, punct p1, punct p0)
{return (long double)(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;
punct aux;

 FILE *fin=freopen("infasuratoare.in","r", stdin);
 FILE *fout=freopen("infasuratoare.out","w", stdout);

 fscanf(fin,"%ld\n", &n);

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

  for (i=2;i<=n;i++)
   {fscanf(fin,"%lf%lf\n", &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;

/*for (i=2;i<=n;i++)
v[i].c=calc_co(v[i],v[1]);*/

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[i]) && h>=2;h--);
  h++;
  sol[h]=i;
  }


printf("%ld\n",h);
for (i=h;i>=1;i--)
 fprintf(fout,"%lf %lf\n", v[sol[i]].x, v[sol[i]].y);

 fclose(fout);
return 0;
}