Cod sursa(job #718566)
#include <cstdio>
#include <algorithm>
using namespace std;
struct point
{
double x,y;
};
point v[120005];
point s1[120005];
point s2[120005];
bool cmp(point a,point b)
{
return (a.x<b.x ||(a.x==b.x && a.y<b.y));
}
bool panta (point a,point b,point c)
{
return (b.y-a.y)*(c.x-a.x)<(b.x-a.x)*(c.y-a.y);
}
int main()
{
freopen("infasuratoare.in","r",stdin);
freopen("infasuratoare.out","w",stdout);
int n,i,k=0,p=0;
scanf("%d",&n);
for(i=1;i<=n;i++)
{
scanf("%lf",&v[i].x);
scanf("%lf",&v[i].y);
}
sort(&v[1],&v[n+1],cmp);
s1[++k]=v[1];
for(i=2;i<=n;i++)
{
while(panta(s1[k-1],s1[k],v[i])&& k>1)
{
k--;
}
s1[++k]=v[i];
}
k--;
s2[++p]=v[n];
for(i=n-1;i>=1;i--)
{
while(panta(s2[p-1],s2[p],v[i]) && p>1)
{
p--;
}
s2[++p]=v[i];
}
p--;
printf("%d\n",p+k);
for(i=p;i>=1;i--)
printf("%.6lf %.6lf\n",s2[i].x,s2[i].y);
for(i=k;i>=1;i--)
printf("%.6lf %.6lf\n",s1[i].x,s1[i].y);
return 0;
}