Cod sursa(job #312110)

Utilizator nicolaetitus12Nicolae Titus nicolaetitus12 Data 5 mai 2009 03:48:48
Problema Infasuratoare convexa Scor 10
Compilator c Status done
Runda Arhiva educationala Marime 1.57 kb
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#define N 120001
double x[N],y[N],c[N];
int idx[N],urm[N],prev[N],n;
int good(double vx,double vy,double ux,double uy)
{if(uy*vx-vy*ux>.0)return 1;
 else return 0;
}
void quick(int st,int dr)
{int s=st,d=dr,aux;
 double p=c[idx[st+rand()%(dr-st+1)]];
 while(s<d)
 {while(c[idx[s]]>p)s++;
  while(c[idx[d]]<p)d--;
  if(s<=d)
  {aux=idx[s];idx[s]=idx[d];idx[d]=aux;
   s++;
   d--;
  }
 }
 if(s<dr)quick(s,dr);
 if(st<d)quick(st,d);
}

int main ()
{int i,imin,numitor,count;
 double aux,minx,miny;
 freopen("infasuratoare.in","r",stdin);
 freopen("infasuratoare.out","w",stdout);
 scanf("%d",&n);
 for (i=1;i<=n;i++)
 {scanf("%lf %lf",&x[i],&y[i]);
 }
 for (i=1;i<=n;i++)idx[i]=i;
 for (i=2,minx=x[1],miny=y[1],imin=1;i<=n;i++)
 {if(miny>x[i])
  {imin=i;minx=x[i];miny=y[i];
  }
  if(miny==y[i])
  {if(minx>x[i])
   {minx=x[i];imin=i;
   }
  }
 }
 aux=x[1];x[1]=x[imin];x[imin]=aux;
 aux=y[1];y[1]=y[imin];y[imin]=aux;
 for (i=2;i<=n;i++)
 {c[i]=(x[i]-minx)/sqrt((x[i]-minx)*(x[i]-minx)+(y[i]-miny)*(y[i]-miny));
 }
 quick(2,n);
 for (i=1;i<n;i++)
 {urm[i]=i+1;
  prev[i+1]=i;
 }
 urm[n]=0;
 i=1;
 while(urm[urm[i]])
 {while(good(x[idx[urm[urm[i]]]]-x[idx[urm[i]]],y[idx[urm[urm[i]]]]-y[idx[urm[i]]],x[idx[urm[i]]]-x[idx[i]],y[idx[urm[i]]]-y[idx[i]]))
  {urm[i]=urm[urm[i]];
   prev[urm[i]]=i;
   i=prev[i];
  }
  i=urm[i];
 }
 for (i=1,count=0;i;i=urm[i])
 {count++;
 }
 printf("%d\n",count);
 
 for (i=1;i;i=urm[i])
 {printf("%lf %lf\n",x[idx[i]],y[idx[i]]);
 }
 return 0;
}