Cod sursa(job #891339)
#include <stdio.h>
# include <algorithm>
# include <math.h>
# include <vector>
#define eps 1e-12
using namespace std;
int n,i,in,c,poz,s[120000],h,ok[120000];
bool use[120000];
struct punct
{
double x; double y;
} p[120000],v[120000];
bool cmp(const punct&a , const punct &b)
{
if (a.x==b.x)
return (a.y<b.y);
return (a.x<b.x);
}
inline int cmp1(double a,double b)
{
if (a+eps<b) return 1;
if (b+eps<a) return -1;
return 0;
}
int semn(punct a, punct b, punct c)
{
double A,B,C;
A=a.y-b.y;
B=b.x-a.x;
C=a.x*b.y-b.x*a.y;
return cmp1(A*c.x+B*c.y+C,0);
}
void rezolva()
{
sort(v+1,v+n+1,cmp);
int k,q;
s[1]=1;
s[2]=2;
ok[2]=1;
k=2;
i=3;
q=1;
while (!ok[1])
{
while (ok[i])
{
if (i==n) q=-1;
i+=q;
}
while (k>=2 && semn (v[s[k-1]],v[s[k]],v[i])==-1)
{
ok[s[k--]]=0;
}
s[++k]=i;
ok[i]=1;
}
h=k-1;
}
int main()
{
freopen("infasuratoare.in","r",stdin);
freopen("infasuratoare.out","w",stdout);
scanf("%d\n",&n);
for (i=1; i<=n; i++)
{
scanf("%lf %lf",&v[i].x,&v[i].y);
}
rezolva();
printf("%d\n",h);
for (i=2; i<=h+1; i++)
printf("%lf %lf\n",v[s[i]].x,v[s[i]].y);
return 0;
}