Cod sursa(job #642955)

Utilizator ProcopliucProcopliuc Adrian Procopliuc Data 2 decembrie 2011 17:22:52
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.61 kb
# include <stdio.h>
# define inf 1000000000.0


int i,n,pozz,mij;

 struct punct 
 {
	 double x,y;
 }a[120005],px,aux;

 double panta (punct y)
 {
	 if (px.x!=y.x)
		 return (y.y-px.y)/(y.x-px.x);
	 else
		 return inf;
 }

 int poz (int i,int j)
 {
	 int ii=0,jj=-1;
	 
	 while (i<j)
	 {
		 if (panta (a[i])>panta(a[j]))
		 {
			 aux=a[i];
			 a[i]=a[j];
			 a[j]=aux;
			 if (ii==1)
			 {
				 ii=0;
				 jj=-1;
			 }
			 else
			 {
				 ii=1;
				 jj=0;
			 }
		 }
		 
		i=i+ii;
		j=j+jj;
	 }
	 return i;
 }
 
 void sort (int i,int j)
 {
	 if (i<j)
	 {
		 mij=(i+j)/2;
		 aux=a[i];
		 a[i]=a[mij];
		 a[mij]=aux;
		 int k=poz(i,j);
		 sort (i,k-1);
		 sort (k+1,j);
	 }
 }
 
 double det (punct x,punct y,punct z)
 {
	 return y.x*z.y+z.x*x.y+x.x*y.y-y.x*x.y-z.x*y.y-z.y*x.x;
 }
 
 
 punct st[120005];
int main ()
{
	freopen ("infasuratoare.in","r",stdin);
    freopen ("infasuratoare.out","w",stdout);
	
	scanf ("%i",&n);
	for (i=1;i<=n;i++)
		scanf ("%lf%lf",&a[i].x,&a[i].y);
	
	
	px.x=inf;
	px.y=inf;
	
	for (i=1;i<=n;i++)
		if (px.x>a[i].x)
		{
			px.x=a[i].x;
			px.y=a[i].y;
			pozz=i;
		}
		else
			if (px.x==a[i].x)
				if (px.y>a[i].y)
				{
					px.x=a[i].x;
					px.y=a[i].y;
					pozz=i;
				}
		
	for (i=pozz;i<n;i++)
		a[i]=a[i+1];
	n--;
	sort (1,n);
	int v=1;
	st[v]=px;
	v++;
	st[v]=a[1];
	for (i=2;i<=n;i++)
	{
		
		while (det (st[v-1],st[v],a[i])<0)
		{
			v--;
			if (v==1)
				break;
		}
		v++;
		st[v]=a[i];
	}
	printf ("%i\n",v);
	for (i=1;i<=v;i++)
		printf ("%lf %lf\n",st[i].x,st[i].y);
	
	return 0;
}