Pagini recente » Cod sursa (job #1329214) | Cod sursa (job #39497) | Cod sursa (job #198676) | Cod sursa (job #1577651) | Cod sursa (job #508882)
Cod sursa(job #508882)
#include<stdio.h>
#include<algorithm>
#define dmax 120004
using namespace std;
int n,w,st[dmax],nr;
struct punct
{ double x;
double y;
double up;
} p[dmax],t;
int sf(punct a, punct b)
{ if(a.up != b.up)
return a.up < b.up;
return a.x < b.x;
}
int pr(int p0, int p1, int p2)
{ double s = (p[p1].x-p[p0].x)*(p[p2].y-p[p0].y)-(p[p2].x-p[p0].x)*(p[p1].y-p[p0].y);
if(s>0)return 1;
return 0;
}
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",&p[i].x,&p[i].y);
w=1;
for(i=2;i<=n;i++)
{ if(p[i].x < p[w].x)
w=i;
else if(p[i].x == p[w].x)
if(p[i].y < p[w].y)
w=i;
}
t=p[1];
p[1]=p[w];
p[w]=t;
for(i=2;i<=n;i++)
p[i].up=(p[i].y-p[1].y)/(p[i].x-p[1].x);
sort(p+2,p+n+1, sf);
st[1]=1;
st[2]=2;
nr=2;
for(i=3;i<=n;i++)
{ while(!pr( st[nr],i,st[nr-1]) && nr>2)
nr--;
st[++nr]=i;
}
printf("%d\n",nr);
for(i=1;i<=nr;i++)
printf("%0.6lf %0.6lf\n",p[st[i]].x,p[st[i]].y);
return 0;
}