Cod sursa(job #270787)
#include<stdio.h>
#include<algorithm>
#define PDD pair<double,double>
using namespace std;
int n;
pair <double, double> nr[120010];
int st[120010];
double pantadr;
/*inline int cmp(double a,double b){
if(a<b)
return -1;
if(b<a)
return 1;
return 0;
}
int cmpP(const PDD &a,const PDD &b){
int r=cmp(a.first,b.first);
if(r)
return r==-1;
return cmp(a.second,b.second)==-1;
}*/
bool scot(int a,int b,int c){
double A=nr[a].second-nr[b].second,B=nr[b].first-nr[a].first,C=nr[a].first*nr[b].second-nr[b].first*nr[a].second;
if(A*nr[c].first + B*nr[c].second + C<0)
return true;
return false;
}
double panta(int i){
double pp=(nr[i].second-nr[1].second)/(nr[i].first-nr[1].first);
return pp;
}
void inf(){
int i=2,vf=2;
st[1]=1;
st[2]=2;
while(i<=n){
++i;
if(panta(i)>pantadr)
continue;
if(vf>=2 && scot(st[vf-1],st[vf],i))
--vf;
st[++vf]=i;
}
i=n;
while(i>1){
--i;
if(panta(i)<pantadr)
continue;
if(vf>=2 && scot(st[vf-1],st[vf],i))
--vf;
st[++vf]=i;
}
printf("%d\n",vf-1);
for(i=1;i<vf;++i)
printf("%.6lf %.6lf\n",nr[st[i]].first,nr[st[i]].second);
}
int main(){
freopen("infasuratoare.in","r",stdin);
freopen("infasuratoare.out","w",stdout);
int i;
scanf("%d",&n);
for(i=1;i<=n;++i)
scanf("%lf%lf",&nr[i].first,&nr[i].second);
sort(nr+1,nr+n+1);
pantadr=(nr[1].second-nr[n].second)/(nr[1].first-nr[n].first);
inf();
fclose(stdin);
fclose(stdout);
return 0;
}