Cod sursa(job #366129)

Utilizator cosgbCosmin cosgb Data 21 noiembrie 2009 01:12:31
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.98 kb
#include <stdio.h>
#include <math.h>
//# define pi 3.1415926535
struct point {double x,y,unghi;};
point aux,ll,pivot,v[120002];
int st[120002];

double pi=3.1415926535;
double dist( point a,point b)
{ double x;
x=sqrt ((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
return x;
}

int prod(point a,point b,point c)
{
    double cp;
    cp=(b.x - a.x)*(c.y - a.y) - (b.y - a.y)*(c.x - a.x);
    if(cp>0) return 1;
    if(cp==0) return 0;
    return -1;
}

long partitionare( long st,long dr)
{long m,i,j;
 m=(st+dr)/2;
 pivot=v[m];
 i=st-1;
 j=dr+1;
 while (1)
 {
	do {++i;}
	       while ((v[i].unghi<pivot.unghi)||(v[i].unghi==pivot.unghi&&dist(v[1],v[i])<dist(v[1],pivot)));
	do {--j;}
	       while ((v[j].unghi>pivot.unghi)||(v[j].unghi==pivot.unghi&&dist(v[1],v[j])>dist(v[1],pivot)));
	if (i<j)
	{aux=v[i];
	 v[i]=v[j];
	 v[j]=aux;
	}
	else
		return j;
 }
}



void quicks( long st,long dr)
{ long p;
  if (st<dr)
    {p=partitionare(st,dr);
     quicks(st,p);
	 quicks(p+1,dr);
	}
}


int main()
{   freopen ("infasuratoare.in","r",stdin);
    freopen ("infasuratoare.out","w",stdout);
	long n,i,poz,varf;
	double t;
	scanf ("%ld",&n);
	scanf ("%lf %lf",&v[1].x,&v[1].y);
	ll=v[1];
	poz=1;
	for (i=2;i<=n;i++)
	  {scanf ("%lf %lf",&v[i].x,&v[i].y);
	       if (ll.y>v[i].y||(ll.y==v[i].y&&ll.x>v[i].x))
		   {ll=v[i];
		    poz=i;
		   }
	  }
	aux=v[poz];
	v[poz]=v[1];
	v[1]=aux;
	
	for (i=2;i<=n;i++)
	 {if (v[i].x!=v[1].x)
		 {t=(v[i].y-v[1].y)/(v[i].x-v[1].x);
	  
	  if (t>=0) v[i].unghi=atan(t);
	    else   v[i].unghi=atan(t)+pi;
		 }
		 else
		    v[i].unghi=pi/2;
	 }
        
	quicks (2,n);
	st[1]=v[1];
	st[2]=v[2];
	varf=2;
	for (i=3;i<=n;i++)
	  {if (prod(st[varf-1],st[varf],v[i])>0)
		   st[++varf]=v[i];
	   while (prod(st[varf-1],st[varf],v[i])<=0)
		   varf--;
	     st[++varf]=v[i];
	  }
	  printf ("%ld\n",varf);
    for (i=1;i<=varf;i++)
		printf ("%lf %lf\n",st[i].x,st[i].y);
		  
return 0;
}