Cod sursa(job #364545)

Utilizator cosgbCosmin cosgb Data 16 noiembrie 2009 09:51:45
Problema Infasuratoare convexa Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 1.93 kb
#include <stdio.h>
#include <math.h>
struct punct {long double x,y;
             };
punct pp,pivot,aux,q[120002],p[120002];			 

int prod(punct a,punct b,punct c)
 {long double p;
  p=((long double)b.x-a.x)*(c.y-b.y)-(b.y-a.y)*(c.x-b.x);
if (p>0)
    return 1;
if (p<0)
    return -1;
	return 0;
 }

 
long double distanta (punct a,punct b)
{ return sqrt((long double)a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);
}


long partitionare(long st,long dr)
 {long i,j,zorro,mijl;
mijl=(st+dr)/2;
pivot=p[mijl];
i=st-1;
j=dr+1;
while (1)
      {
       do {i++;
		   zorro=prod(p[1],p[i],pivot);
	      }
	   while (zorro>0 || (zorro==0&&distanta(p[1],pivot)>distanta(p[1],p[i])));
       do {j--;
		   zorro=prod(p[1],pivot,p[j]);
	      }
	   while (zorro>0 || (zorro==0&&distanta(p[1],p[j])>distanta(p[1],pivot)));
       if (i<j)
          {aux=p[i];
           p[i]=p[j];
           p[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,varf,poz;  
  scanf ("%ld",&n);
  scanf ("%Lf%Lf",&p[1].x,&p[1].y);
  pp=p[1];
  poz=1;
  for (i=2;i<=n;i++)
    { scanf ("%Lf%Lf",&p[i].x,&p[i].y);
        if ((p[i].x<pp.x)||(p[i].x==pp.x&&p[i].y<pp.y))
		     {pp=p[i];
		     poz=i;
		     }
	}
  aux=p[poz];
  p[poz]=p[1];
  p[1]=aux;
  quicks(2,n);
  q[1]=p[1];
  q[2]=p[2];
  varf=2;
  for (i=3;i<=n;i++)
   {
	   if (prod(q[varf-1],q[varf],p[i])>=0)
	      {varf++;
	       q[varf]=p[i];
		  }
		  else
           {while (prod (q[varf-1],q[varf],p[i])<0 && varf >2)
             varf--;
             varf++;
			 q[varf]=p[i];
		   }
   }
	printf ("%ld\n",varf);
    for (i=1;i<=varf;i++)
		printf ("%.6Lf %.6Lf\n",q[i].x,q[i].y);

	
  return 0;
}