Pagini recente » Cod sursa (job #569147) | Cod sursa (job #2406181) | Cod sursa (job #1119080) | Cod sursa (job #948868) | Cod sursa (job #411953)
Cod sursa(job #411953)
#include <stdio.h>
#define Nmax 220100
struct P { double x,y; };
P a[Nmax];
int st[Nmax], vf, n;
inline int cmp_(P a, P b)
{
if (a.y > b.y) return 1;
if (a.y < b.y) return -1;
if (a.x > b.x) return 1;
if (a.x < b.x) return -1;
return 0;
}
inline int sens(P A,P B, P C)
{
double semn = ((B.x-A.x)*(C.y-A.y)-(B.y-A.y)*(C.x-A.x));
if (semn < 0) return -1;
if (semn > 0) return 1;
return 0;
}
inline int cmp(P A,P B)
{
return sens(a[1],A,B);
}
void sort(int st,int dr)
{
int i=st,j=dr;
P sch=a[(i+j)/2], tmp;
do {
while (cmp(a[i],sch) == 1) ++i;
while (cmp(sch,a[j]) == 1) --j;
if (i<=j)
{
tmp = a[i];
a[i] = a[j];
a[j] = tmp;
++i; --j;
}
} while (i<=j);
if (st<j) sort(st,j);
if (i<dr) sort(i,dr);
}
int main()
{
freopen("infasuratoare.in","r",stdin);
freopen("infasuratoare.out","w",stdout);
scanf("%d", &n);
for (int i=1;i<=n;++i)
scanf("%lf%lf", &a[i].x, &a[i].y);
for (int i=2;i<=n;++i)
if (cmp_(a[1],a[i])==1)
{
a[0] = a[1];
a[1] = a[i];
a[i] = a[0];
}
sort(2,n);
st[++vf] = 1;
for (int i=2;i<=n;++i)
{
while (vf > 1 && sens(a[st[vf-1]],a[st[vf]],a[i]) == -1)
--vf;
st[++vf] = i;
}
while (vf > 1 && sens(a[st[vf]],a[st[vf]],a[1]) == -1) --vf;
printf("%d\n", vf);
for (int i=1;i<=vf;++i)
printf("%.6f %.6f\n", a[st[i]].x, a[st[i]].y);
return 0;
}