Pagini recente » Cod sursa (job #1711773) | Cod sursa (job #447193) | Cod sursa (job #830276) | Cod sursa (job #2618250) | Cod sursa (job #455287)
Cod sursa(job #455287)
#include<stdio.h>
#include<algorithm>
using namespace std;
#define eps 1e-12
int n,k,st[120005];
short int fol[120005];
struct point
{
double x,y;
};
point v[120005];
int compar(double a,double b)
{
if(a+eps < b) return -1;
if(b+eps < a) return 1;
return 0;
}
int cmp(const point& a,const point& b)
{
if(!compar(a.y,b.y))
return (compar(a.x,b.x)==-1);
return (compar(a.y,b.y)==-1);
}
int plan(point A,point B,point C)
{
double a,b,c;
a=A.y-B.y;
b=B.x-A.x;
c=A.x*B.y-A.y*B.x;
return (compar(a*C.x+b*C.y+c,0));
}
int main ()
{
int i;
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);
k=2;
st[1]=1;st[2]=2;
for(i=3;i<=n;i++)
{
while(k >= 2 && plan(v[st[k-1]],v[st[k]],v[i])<=0)
--k;
st[++k] = i;
}
for(i=1;i<=k;i++)
fol[st[i]]=1;
fol[1]=0;
for(i=n;i>=1;i--)
{
if(fol[i])
continue;
while(k>=2 && plan(v[st[k-1]],v[st[k]],v[i])<=0)
--k;
st[++k]=i;
}
printf("%d\n",k-1);
for(i=1;i<k;i++)
printf("%.6lf %.6lf\n",v[st[i]].x,v[st[i]].y);
return 0;
}