Cod sursa(job #313082)

Utilizator taloibogdanTaloi Bogdan Cristian taloibogdan Data 7 mai 2009 22:14:51
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.75 kb
#include<stdio.h>
#include<math.h>
#define eps 0.0000000000001
struct POINT
{
 double x,y;
}a[125000],min;
struct LINIEC
{
 double a,b,c;
};
double p[125000];
long n,st[125000],i,sc;
long partit(double p[],POINT a[ ],long st, long dr)
{long i,j,m;
 double piv,pp;
 POINT aa;
 m=(st+dr)/2;
 piv=p[m];
 i=st-1;
 j=dr+1;
 while(1)
  {do{++i;} while(p[i]<piv);
   do{--j;} while(p[j]>piv);
   if (i<j)
	 {pp=p[i];p[i]=p[j];p[j]=pp;aa=a[i];a[i]=a[j];a[j]=aa;}
	   else
	 return j;
  }
}
void quicks(double p[],POINT a[ ],long st,long dr)
{long pp;
 if (st<dr)
   {pp=partit(p,a,st,dr);
    quicks(p,a,st,pp);
    quicks(p,a,pp+1,dr);}
}
long ccw(POINT A,POINT B,POINT C)
{
 /*1 daca sensul e trigonometric
   -1 daca sensul e orar
   0 daca A,B,C colineare*/
double p;
p=(B.x-A.x)*(C.y-B.y)-(B.y-A.y)*(C.x-B.x);
if(fabs(p)<eps)return 0;
if(p>=eps)return  1;
return -1;
}

int main()
{
 freopen("infasuratoare.in","r",stdin);
 freopen("infasuratoare.out","w",stdout);
 scanf("%ld",&n);
 min.x=2000000005;
 min.y=2000000005;
 for(i=1;i<=n;++i)
    {scanf("%lf%lf",&a[i].x,&a[i].y);
     if(a[i].x<min.x||(a[i].x==min.x&&a[i].y<min.y))min=a[i];}
 sc=0;
 for(i=1;i<=n-sc;++i)
    {while(a[i+sc].x==min.x&&a[i+sc].y==min.y)++sc;
     if(i+sc<=n)
     {a[i]=a[i+sc];
      a[i].x-=min.x;
      a[i].y-=min.y;
      if(fabs(a[i].x)<eps)p[i]=2000000001;
                     else p[i]=a[i].y/a[i].x;}}
 n-=sc;
 quicks(p,a,1,n);
 st[++st[0]]=1;
 st[++st[0]]=2;
 for(i=3;i<=n;++i)
    {while(st[0]>=2&&ccw(a[st[st[0]-1]],a[st[st[0]]],a[i])!=1)--st[0];
     st[++st[0]]=i;}
 printf("%ld\n%.6lf %.6lf\n",st[0]+1,min.x,min.y);
 for(i=1;i<=st[0];++i)
    printf("%.6lf %.6lf\n",a[st[i]].x+min.x,a[st[i]].y+min.y);
 return 0;
}