Cod sursa(job #276719)
#include<stdio.h>
#include<stdlib.h>
#define EPS 1e-12
#define Nmax 120002
struct Punct
{
double x,y;
};
Punct c[Nmax], a[Nmax];
int st[Nmax];
int H,n;
Punct sol[Nmax];
void read()
{
int i;
scanf("%d",&n);
for(i=1;i<=n;++i)
scanf("%lf%lf",&c[i].x,&c[i].y);
}
inline int comp(double a, double b)
{
if(a+EPS < b) return -1;//a<b
if(b+EPS < a) return 1; //a>b
return 0; // a==b
}
int cmp(const void*a, const void*b)
{
int x=*(int*)a, y=*(int*)b;
int r=comp(c[x].x, c[y].x);
if(!r)
{
int k=comp(c[x].y, c[y].y);
return k;
}
return r;
}
void sortare()
{
int i,h[Nmax];
for(i=0;i<=n;++i) h[i]=i;
c[0].x=c[0].y=-1000000003;
qsort(h,n+1,sizeof(int),cmp);
for(i=1;i<=n;++i) a[i]=c[h[i]];
}
int viz[Nmax];
inline int tre_scos(Punct A, Punct B, Punct C)
{
double det = A.x*B.y + B.x*C.y + A.y*C.x;
det -= ( B.y*C.x + A.y*B.x + C.y*A.x );
if(det<0) return -1;
if(det==0) return 0;
return 1;
}
void convex()
{
int pas=1,i,k=0;
viz[2]=1; st[1] = 1; st[2] = 2; k=2; i=3;
while(!viz[1])
{
while(viz[i])
{
if(i==n) pas=-1;
i+=pas;
}
while(k>=2 && tre_scos(a[st[k-1]], a[st[k]], a[i]) == -1) viz[st[k--]] = 0;
st[++k] = i; viz[i] = 1;
}
H = k-1;
printf("%d\n",H);
for(i=1;i<=H;++i) printf("%.6lf %.6lf\n",a[st[i]].x, a[st[i]].y);
}
int main()
{
freopen("infasuratoare.in","r",stdin);
freopen("infasuratoare.out","w",stdout);
read();
sortare();
convex();
return 0;
}