Cod sursa(job #889571)
#include<cstdio>
#include<vector>
#include<algorithm>
#include<fstream>
#include<cmath>
#define EPS 0.000001
using namespace std;
int n,P0,vf;
struct Punct{double x,y;};
Punct P[120010],St[120010];
inline double Dist(Punct A)
{
return sqrt((A.x-P[1].x)*(A.x-P[1].x)+(A.y-P[1].y)*(A.y-P[1].y));
}
inline bool Sortare(Punct A,Punct B)
{
if(abs((A.x-P[1].x)*(B.y-P[1].y)-(B.x-P[1].x)*(A.y-P[1].y))<=EPS)
return Dist(A)<Dist(B);
return (A.x-P[1].x)*(B.y-P[1].y)<(B.x-P[1].x)*(A.y-P[1].y);
}
inline double Intoarcere(Punct A,Punct B,Punct C)
{
return (A.x*B.y+B.x*C.y+C.x*A.y-C.x*B.y-B.x*A.y-A.x*C.y);
}
int main()
{
int i;
freopen("infasuratoare.in","r",stdin);
scanf("%d",&n);
//determin la citire punctul cel mai de jos,cel mai din stanga in caz de egalitate
P0=1;
for(i=1;i<=n;i++)
{
scanf("%lf %lf",&P[i].x,&P[i].y);
if(P[i].y>P[P0].y || (P[i].y==P[P0].y && P[i].x>P[P0].x))
P0=i;
}
//selectez toate punctele in afara de P0 pentru a le sorta
swap(P[1],P[P0]);
sort(P+2,P+n+1,Sortare);
//bag punctele in stiva
St[vf]=P[1];
for(i=2;i<=n;i++)
{
while(vf>=1 && Intoarcere(St[vf-1],St[vf],P[i])>0.0)
{
//daca punctul curent face cu ultimele 2 puncte din stiva o intoarcere spre dreapta
//atunci este scos din infasuratoare punctul din varful stivei
vf--;
}
St[++vf]=P[i];
}
//afisez punctele de pe infasuratoarea convexa
freopen("infasuratoare.out","w",stdout);
printf("%d\n",vf+1);
for(i=vf;i>=0;i--)
printf("%lf %lf\n",St[i].x,St[i].y);
return 0;
}