Cod sursa(job #393511)
#include<cstdio>
#include<cstring>
#include<algorithm>
#define x first
#define y second
using namespace std;
const char iname[]="infasuratoare.in";
const char oname[]="infasuratoare.out";
const int maxn=120000;
int n,i,j,s[maxn],been[maxn],step,k;
pair<double,double> P[maxn];
double eps=1e-12;
int cmp(double x,double y)
{
if(x+eps<y)
return -1;
if(y+eps<x)
return 1;
return 0;
}
bool operator<(pair<double,double> a,pair<double,double> b)
{
int d=cmp(a.x,b.x);
if(d)
return d==-1;
return cmp(a.y,b.y)==-1;
}
double area(pair<double,double> a,pair<double,double> b,pair<double,double> c)
{
return a.x*b.y-a.y*b.x+b.x*c.y-b.y*c.x+c.x*a.y-c.y*a.x;
}
int main()
{
freopen(iname,"r",stdin);
freopen(oname,"w",stdout);
scanf("%d",&n);
for(i=0;i<n;++i)
scanf("%lf %lf",&P[i].x,&P[i].y);
sort(P,P+n);
s[0]=0;
s[1]=1;
been[1]=1;
step=1;
k=1;
i=step;
while(been[0]==0)
{
if(i==n-1)
step=-1;
while(been[i])
i+=step;
while(k&&cmp(area(P[s[k-1]],P[s[k]],P[i]),0)<=0)
been[s[k--]]=0;
been[s[++k]=i]=1;
}
printf("%d\n",k);
for(i=1;i<=k;++i)
printf("%.6lf %.6lf\n",P[s[i]].x,P[s[i]].y);
fclose(stdin);
fclose(stdout);
return 0;
}