Pagini recente » Cod sursa (job #3123651) | Cod sursa (job #1941758) | Cod sursa (job #2965438) | Cod sursa (job #394027) | Cod sursa (job #256690)
Cod sursa(job #256690)
#include <stdio.h>
#include <math.h>
struct punct{double x,y;};
punct v[120000];
long n,h,sol[120000];
long poz2(long li, long ls)
{long i0=0,j0=-1,aux;
punct a;
while (li<ls)
{if ((v[ls].x-v[1].x)*(v[li].y-v[1].y)<(v[li].x-v[1].x)*(v[ls].y-v[1].y))
{a=v[li];
v[li]=v[ls];
v[ls]=a;
aux=-j0;
j0=-i0;
i0=aux;
}
li+=i0;
ls+=j0;
}
return li;
}
void sort2(long li, long ls)
{long k;
if (li<ls)
{k=poz2(li,ls);
sort2(li,k-1);
sort2(k+1,ls);
}
}
int verif(punct p2, punct p1, punct p0)
{return (p2.x*p1.y+p1.x*p0.y+p0.x*p2.y-p0.x*p1.y-p2.x*p0.y-p1.x*p2.y<0);
}
int main()
{long i,j;
punct aux;
freopen("infasuratoare.in","r", stdin);
freopen("infasuratoare.out","w", stdout);
scanf("%d", &n);
scanf("%lf %lf", &v[1].x,&v[1].y);
j=1;
for (i=2;i<=n;i++)
{scanf("%lf %lf", &v[i].x,&v[i].y);
if (v[i].x<v[j].x || (v[i].x==v[j].x && v[i].y<v[j].y))
j=i;
}
aux=v[j];
v[j]=v[1];
v[1]=aux;
sort2(2,n);
sol[1]=1;
sol[2]=2;
h=2;
for (i=3;i<=n;i++)
{for (;!verif(v[sol[h-1]],v[sol[h]],v[sol[i]]) && h>2;h--);
h++;
sol[h]=i;
}
printf("%d\n",h);
for (i=1;i<=h;i++)
printf("%lf %lf\n", v[sol[i]].x, v[sol[i]].y);
return 0;
}