Cod sursa(job #711271)
#include<fstream>
#include<algorithm>
#include<iomanip>
using namespace std;
#define INF 1000000010
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
struct cel{double x, y;};
int n,i,poz,k,stv[130000];
double minx=INF,miny=INF;
cel v[130000],aux;
inline int scoate(double x1, double y1, double x2, double y2, double x3, double y3)
{long double x = ((long double)x2-x1)*(y3-y1)-(x3-x1)*(y2-y1);
if(x >= 0)
return 1;
return 0;
}
inline bool cmp(cel a, cel b)
{ if ((a.x * b.y) > (a.y * b.x))
return true;
else
return false;
}
int main()
{ fin >> n;
v[0].x = INF;
v[0].y = INF;
for(i=1;i<=n;i++)
{ fin >> v[i].x >> v[i].y;
if (v[i].x < v[poz].x)
poz = i;
else
if (v[i].x == v[poz].x )
if (v[i].y < v[poz].y )
poz = i;
}
aux = v[poz];
v[poz]=v[1];
v[1]=aux;
minx = v[1].x;
miny = v[1].y;
for(i=1;i<= n;i++)
{ v[i].x -= minx;
v[i].y -= miny;
}
sort(v+2,v+n+1,cmp);
stv[1]=1;
stv[2]=2;
k = 2;
for(i=3;i<=n;i++)
{ while( k>=2 && scoate(v[i].x,v[i].y,v[stv[k]].x,v[stv[k]].y,v[stv[k-1]].x,v[stv[k-1]].y) )
k--;
stv[++k] = i;
}
fout << k << '\n';
fout << setprecision(16);
for(i=1;i<=k;i++)
fout << v[stv[i]].x + minx << " " << v[stv[i]].y + miny << '\n';
return 0;
}