Pagini recente » Cod sursa (job #1048834) | Cod sursa (job #2631667) | Cod sursa (job #1337606) | Cod sursa (job #2332754) | Cod sursa (job #1827434)
#include <bits/stdc++.h>
using namespace std;
const int N=120005;
const double eps=1e-12;
int i,n,st[N],pos=2,r=1;
struct Point{
double x,y;
} v[N];
bool cmp(Point a, Point b){
if(a.y==b.y) return a.x<b.x;
return a.y<b.y;
}
int ccw(Point P1,Point P2,Point P3){
double cp=(P2.x-P1.x)*(P3.y-P1.y)-(P2.y-P1.y)*(P3.x-P1.x);
if(fabs(cp)<eps) return 0;
if(cp>eps) return 1;
return -1;
}
int main()
{
freopen("infasuratoare.in","r",stdin);
freopen("infasuratoare.out","w",stdout);
scanf("%d",&n);
for(i=1;i<=n;i++) scanf("%lf%lf",&v[i].x,&v[i].y);
sort(&v[1],&v[n+1],cmp);
st[1]=1, st[2]=2;
for(i=3;i>0;i+=r){
if(i==n) r=-1;
while(pos>=2 and ccw(v[st[pos-1]], v[st[pos]], v[i])==-1) pos--;
st[++pos]=i;
}
printf("%d\n",--pos);
for(i=1;i<=pos;i++) printf("%lf %lf\n",v[st[i]].x,v[st[i]].y);
return 0;
}