Cod sursa(job #799462)
#include <cstdio>
#include <algorithm>
using namespace std;
FILE *f,*g;
struct cp{double x,y;} ax;
cp v[100100];
int st[100100];
int i,n,mni;
double mnx,mny;
bool cmp(cp a, cp b)
{
return ((double)(a.y-mny)*(b.x-mnx)<=(double)(a.x-mnx)*(b.y-mny));
}
int smn(cp a , cp b, cp c)
{
long double s=0;
s=(long double)a.x*b.y+ b.x*c.y+ c.x*a.y - a.y*b.x- b.y*c.x- c.y*a.x;
if (s<0)
return 0;
return 1;
}
int main()
{
f=fopen("infasuratoare.in","r");
g=fopen("infasuratoare.out","w");
fscanf(f,"%d",&n);
for (i=1;i<=n;i++)
{
fscanf(f,"%lf %lf",&v[i].x,&v[i].y);
if (i==1)
{
mnx=v[i].x;
mny=v[i].y;
}
if (v[i].x<mnx || (v[i].x==mnx && v[i].y<mny))
{
mnx=v[i].x;
mny=v[i].y;
mni=i;
}
}
cp ax;
ax=v[mni];
v[mni]=v[1];
v[1]=ax;
sort(v+2,v+n+1,cmp);
st[0]=2;
st[1]=1;
st[2]=2;
for (i=3;i<=n;i++)
{
while (st[0]>=1 && smn(v[st[st[0]-1]],v[st[st[0]]],v[i])==0)
st[0]--;
st[++st[0]]=i;
}
fprintf(g,"%d\n",st[0]);
for (i=1;i<=st[0];i++)
fprintf(g,"%.6lf %.6lf\n",v[st[i]].x,v[st[i]].y);
fclose(g);
return 0;
}