Cod sursa(job #409805)

Utilizator petrecgClinciu Glisca Petre petrecg Data 3 martie 2010 21:19:53
Problema Infasuratoare convexa Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 1.2 kb
#include <stdio.h>
double x[120010],y[120010];
long v[120010],st[120010],b[120010],c[120010],i,k,m,n,pas,h,uz[120010];

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)
{if(x[i]<x[j]||(x[i]==x[j]&&y[i]<y[j]))return 1;
 return 0;
}

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(i,j)))
     {b[k++]=x[i++];c[k-1]=y[i-1];}
    else
     {b[k++]=x[j++];c[k-1]=y[j-1];}
   for(k=st;k<=dr;k++){x[k]=b[k];y[k]=c[k];}
  }
}

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