Cod sursa(job #455436)

Utilizator elfusFlorin Chirica elfus Data 13 mai 2010 19:55:45
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.53 kb
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#define EPS 0.0000000001
#define ELFMAX 120012
struct ELF
{
double x,y;
};
ELF v[ELFMAX],conv[ELFMAX];
int ccw(ELF A,ELF B,ELF C)
{
double val;
val=(B.x-A.x)*(C.y-B.y)-(B.y-A.y)*(C.x-B.x);
if(fabs(val)<EPS)
  return 0;
if(val>=EPS)
 return 1;

return -1;
}
void swap(int a,int b)
{
ELF aux;
aux=v[a];
v[a]=v[b];
v[b]=aux;
}
int same_point(ELF a,ELF b)
{
return (fabs(a.x-b.x)<EPS && fabs(a.y-b.y)<EPS);
}
double dist(ELF a,ELF b)
{
return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
int comp(const void *a,const void *b)
{
double d1,d2;
int d;
ELF *pa,*pb;
pa=(ELF*)a;
pb=(ELF*)b;
if(same_point(*pa,*pb))
  return 0;
d=ccw(v[1],*pa,*pb);
if(d==1)
  return -1;
if(d==0)
  {
  d1=dist(v[1],*pa);
  d2=dist(v[1],*pb);
  if(d1-d2<=-EPS)
     return -1;
  else
     return 1;
  }
return 1;
}
int main()
{
int n,i;
freopen("infasuratoare.in","r",stdin);
freopen("infasuratoare.out","w",stdout);
scanf("%d",&n);
scanf("%lf%lf",&v[1].x,&v[1].y);
for(i=2;i<=n;i++)
  {
  scanf("%lf%lf",&v[i].x,&v[i].y);
  if(  (fabs(v[i].y-v[1].y)<EPS && (v[i].x-v[1].x)<=-EPS) || (v[i].y-v[1].y<=-EPS))
      {swap(1,i);}
  }
qsort(v+2,n-1,sizeof(v[0]),comp);
conv[1]=v[1]; conv[2]=v[2]; v[n+1]=v[1];
int top=2,u=3;
while(u<=n+1)
 {
 if(ccw(conv[top-1],conv[top],v[u])>0)
   {
	   conv[++top]=v[u];
	   u++;
   }
 else
   top--;
 
 }
printf("%d\n",top-1);
for(i=1;i<=top-1;i++)
  printf("%.6Lf %.6Lf\n",conv[i].x,conv[i].y);
return 0;
}