Pagini recente » Cod sursa (job #641296) | Cod sursa (job #2609712) | Cod sursa (job #155836) | Cod sursa (job #1796442) | Cod sursa (job #409652)
Cod sursa(job #409652)
#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;
}