Cod sursa(job #409652)

Utilizator petrecgClinciu Glisca Petre petrecg Data 3 martie 2010 19:42:13
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.19 kb
#include <stdio.h>
double x[120010],y[120010];
long v[120010],st[120010],b[120010],i,k,m,n,p;
long double semn(long i1,long i2,long i3)
{return (long double)x[i1]*y[i2]+x[i2]*y[i3]+x[i3]*y[i1]-y[i1]*x[i2]-y[i2]*x[i3]-y[i3]*x[i1];
}

int cmp(long i,long j)
{return (double)(x[i]-x[p])*(y[j]-y[p])<(double)(x[j]-x[p])*(y[i]-y[p]);
}

void merge_sort(long st,long dr)
{long mij=st+((dr-st)>>1),i,j,k;
 if(st!=dr)
  {merge_sort(st,mij);
   merge_sort(mij+1,dr);
   for(i=st,j=mij+1,k=st;i<=mij||j<=dr;)
    if(j>dr||(i<=mij&&cmp(v[i],v[j])))
     {b[k++]=v[i++];}
    else
     {b[k++]=v[j++];}
   for(k=st;k<=dr;k++){v[k]=b[k];}
  }
}

int main()
{freopen("infasuratoare.in","r",stdin);
 freopen("infasuratoare.out","w",stdout);
 scanf("%ld",&n);
 x[0]=1000000001;y[0]=1000000001;
 p=0;
 for(i=1;i<=n;i++)
  {scanf("%lf%lf",&x[i],&y[i]);
   if(x[i]<x[p]||(x[i]==x[p]&&y[i]==y[p]))p=i;
  }
 for(i=1;i<=n;i++)if(i!=p)v[++m]=i;
 merge_sort(1,m);
 k=1;st[k]=p;
 for(i=1;i<=m;i++)
  {while(k>=2&&semn(st[k-1],st[k],v[i])>0)k--;
   k++;st[k]=v[i];
  }
 printf("%ld\n",k);k++;st[k]=p;
 for(i=k-1;i>=1;i--)printf("%lf %lf\n",x[st[i]],y[st[i]]);
 fclose(stdin);fclose(stdout);
 return 0;
}