Cod sursa(job #475834)
#include <cstdio>
#include <algorithm>
using namespace std;
#define DN 120005
struct punct {
double x; double y;
} siri[DN];
int n;
int cmp(double a,double b) {
if(a<b) return -1;
if(b<a) return 1;
return 0;
}
int cmp_sort(const punct &a,const punct &b) {
int r=cmp(a.x,b.x);
if(r) return r==-1;
return cmp(a.y,b.y)==-1;
}
int pointLocation(punct a, punct b,punct c) {
double A,B,C;
A=a.y-b.y;
B=b.x-a.x;
C=a.x*b.y-b.x*a.y;
double rez=A*c.x+B*c.y+C;
return cmp(rez,0);
}
void in() {
int ind=1,fol[DN],i=3,stiva[DN],vf=2;
fol[2]=1; stiva[1]=1; stiva[2]=2;
while(!fol[1]) {
while(fol[i] ) {
if(i==n) ind=-1;
i+=ind;
}
while(vf>=2 && pointLocation(siri[stiva[vf-1]],siri[stiva[vf]],siri[i])==-1) fol[stiva[vf--]]=0;
stiva[++vf]=i;
fol[i]=1;
}
printf("%d\n",vf-1);
for(i=1; i<vf; ++i) printf("%.6lf %.6lf\n",siri[stiva[i]].x,siri[stiva[i]].y);
}
int main()
{
freopen("infasuratoare.in","r",stdin);
freopen("infasuratoare.out","w",stdout);
scanf("%d",&n);
for(int i=1; i<=n; ++i) scanf("%lf %lf",&siri[i].x,&siri[i].y);
sort(siri+1,siri+n+1,cmp_sort);
in();
return 0;
}