Pagini recente » Cod sursa (job #1856067) | Cod sursa (job #2490324) | Cod sursa (job #448876) | Cod sursa (job #1263932) | Cod sursa (job #409805)
Cod sursa(job #409805)
#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;
}