Cod sursa(job #889355)
#include<cstdio>
using namespace std;
#define nmax 120010
struct pct
{
double x;
double y;
} a[nmax],A,B,C,D;
int n,ok[nmax],s[nmax],qp[7],q,l,tginf,i,k;
double tg;
int ap_dr(pct a,pct b,pct c)
{
pct z;
if(a.x>b.x)
{
z.x=a.x;
z.y=a.y;
a.x=b.x;
a.y=b.y;
b.x=z.x;
b.y=z.y;
}
if(a.y>b.y)
{
if(c.x>=a.x && c.x<=b.x && c.y<=a.y && c.y>=b.y)
return 1;
else
return 0;
}
else
{
if(c.x>=a.x && c.x<=b.x && c.y<=b.y && c.y>=a.y)
return 1;
else
return 0;
}
}
int main()
{
freopen("infasuratoare.in","r",stdin);
freopen("infasuratoare.out","w",stdout);
scanf("%d",&n);
for(i=1;i<=n;i++)
{
scanf("%lf%lf",&a[i].x,&a[i].y);
if(i==1)
{
A.x=B.x=C.x=D.x=a[i].x;
A.y=B.y=C.y=D.y=a[i].y;
qp[1]=qp[2]=qp[3]=qp[4]=qp[5]=1;
}
if(A.y>a[i].y || (A.y==a[i].y && A.x>a[i].x))
{
A.x=a[i].x;
A.y=a[i].y;
qp[1]=qp[5]=i;
}
if(B.x<a[i].x || (B.x==a[i].x && B.y>a[i].y))
{
B.x=a[i].x;
B.y=a[i].y;
qp[2]=i;
}
if(C.y<a[i].y || (C.y==a[i].y && C.x<a[i].x))
{
C.x=a[i].x;
C.y=a[i].y;
qp[3]=i;
}
if(D.x>a[i].x || (D.x==a[i].x && D.y<a[i].y))
{
D.x=a[i].x;
D.y=a[i].y;
qp[4]=i;
}
}
s[++k]=qp[1];
ok[qp[1]]=1;
pct p1,p2,p3;
p1.x=A.x;
p1.y=A.y;
p2.x=B.x;
p2.y=B.y;
l=2;
//tginf=1;
while(ok[qp[1]]!=2)
{
tg=120000;
for(i=1;i<=n;i++)
{
if((ok[i]!=1 && ap_dr(p1,p2,a[i])) || (i==qp[1] && p1.x!=A.x && p1.y!=A.y))
{
if(a[i].x-p1.x==0)
{
if((p3.y<a[i].y && l==3) || (p3.y>a[i].y && l==5) || tginf==0)
{
p3.x=a[i].x;
p3.y=a[i].y;
q=i;
tginf=1;
}
}
if(a[i].x-p1.x!=0 && tginf==0)
{
if((a[i].y-p1.y)/(a[i].x-p1.x)<tg)
{
tg=(a[i].y-p1.y)/(a[i].x-p1.x);
p3.x=a[i].x;
p3.y=a[i].y;
q=i;
}
else
{
if((a[i].y-p1.y)/(a[i].x-p1.x)==tg)
{
if((a[i].y>p3.y && l==3) || (a[i].y<p3.y && l==5))
{
p3.x=a[i].x;
p3.y=a[i].y;
q=i;
}
}
}
}
}
}
s[++k]=q;
ok[q]++;
tginf=0;
if(p3.x==p2.x && p3.y==p2.y)
{
p1.x=p2.x;
p1.y=p2.y;
p2.x=a[qp[++l]].x;
p2.y=a[qp[l]].y;
}
else
{
p1.x=p3.x;
p1.y=p3.y;
}
}
printf("%d\n",k-1);
for(i=1;i<k;i++)
printf("%lf %lf\n",a[s[i]].x,a[s[i]].y);
return 0;
}