Cod sursa(job #399215)

Utilizator me_andyAvramescu Andrei me_andy Data 20 februarie 2010 00:14:59
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.3 kb
#include<stdio.h>
#include<math.h>
#include<search.h>
#define max 120001



int i,j,min,n,px,py,vect[max],st[max];
double vx[max],vy[max],up[max];

int sort_function(const void *x,const void *y)
{ int a,b;
  a=*(int *)x;
  b=*(int *)y;
  if( up[a]- up[b]>0)
   return 5454;
  else return -58;
}

long double  semn(int a,int b, int c)
{
 return (long double) ( vx[a]*vy[b]+vx[b]*vy[c]+vx[c]*vy[a]-vy[a]*vx[b]-vy[b]*vx[c]-vy[c]*vx[a]);
}


int main()
{
 	freopen("infasuratoare.in","r",stdin);
	freopen("infasuratoare.out","w",stdout);


 scanf("%d\n",&n);
 scanf("%lf %lf",&vx[1],&vy[1]);
 min=1;
 vect[1]=1;
 for(i=2;i<=n;i++)
 {
 scanf("%lf %lf",&vx[i],&vy[i]);
  if(vy[i]<vy[min] || ( vy[i]==vy[min] && vx[i]<vx[min]))
   min=i;
  vect[i]=i;
 }

 px=vx[min];
 py=vy[min];

   for(i=1;i<=n;i++)
 {
  if(i!=min)
  {
  double aux=pow(vx[i]-px,2)+pow(vy[i]-py,2);
  aux=sqrt(aux);
  up[i]=(double)(px-vx[i])/aux;
 }}

 qsort(vect+1, n, sizeof(vect[1]),sort_function);
 st[1]=min;
 st[2]=vect[1];
 st[3]=vect[2];
 j=3;
 for(i=3;i<=n;i++)
 {
  if(vect[i]!=min)
  {
   while(j>=2 && semn(st[j-1],st[j],vect[i])<0) --j;
  st[++j]=vect[i];
  }
 }

 st[0]=min;
printf("%d\n",j);
 for(i=1;i<=j;i++)
 {
  printf("%lf %lf\n",vx[st[i]],vy[st[i]]);

 }

 return 0;
}