Cod sursa(job #412304)
#include <stdio.h>
#include <algorithm>
using namespace std;
const int size = 120010;
struct pct
{
double x,y;
}A[size],P1,rez[size];
int n,poz;
double panta(pct b,pct c)
{
return (b.x-P1.x)*(c.y-P1.y) - (b.y-P1.y)*(c.x-P1.x)>0;
}
double panta2(pct P1,pct b,pct c)
{
return (b.x-P1.x)*(c.y-P1.y) - (b.y-P1.y)*(c.x-P1.x)>0;
}
struct cmp
{
bool operator()(const pct &a,const pct &b)const
{
return panta(a,b)>0;
}
};
void solve()
{
scanf ("%d",&n);
P1.y=0x3f3f3f;
for (int i=0;i<n;i++)
{
scanf ("%lf %lf",&A[i].x , &A[i].y);
if (A[i].y<P1.y || (A[i].y==P1.y && A[i].x<P1.x) )
{
P1=A[i];
poz=i;
}
}
pct aux=A[poz];
A[poz]=A[0];
A[0]=aux;
sort(A+1,A+n,cmp());
rez[1]=A[0];
rez[2]=A[1];
rez[3]=A[2];
int nr=3;
for (int i=3;i<n;i++)
{
while (nr>2 && panta2(rez[nr],A[i],rez[nr-1])<=0)
nr--;
rez[++nr]=A[i];
}
printf("%d\n",nr);
for (int i=1;i<=nr;i++)
printf("%lf %lf\n",rez[i].x,rez[i].y);
}
int main ()
{
freopen ("infasuratoare.in","r",stdin);
freopen ("infasuratoare.out","w",stdout);
solve();
return 0;
}