Pagini recente » Cod sursa (job #885538) | Cod sursa (job #2592810) | Cod sursa (job #1211011) | Cod sursa (job #773793) | Cod sursa (job #270316)
Cod sursa(job #270316)
#include <stdio.h>
#include <math.h>
#define Nmax 120001
struct Punct { double x, y; } pct[Nmax];
int N, i, jos, a[Nmax];
int st[Nmax], vf;
inline int comp(Punct a, Punct b) { return atan2(a.y - pct[jos].y, a.x - pct[jos].x) > atan2(b.y - pct[jos].y, b.x - pct[jos].x) ? 1 : 0; }
inline void swap(int &a, int &b) { int tmp = a; a = b; b = tmp; }
void sort(int p, int q)
{
int st = p, dr = q;
Punct m = pct[a[(st + dr) >> 1]];
while (st < dr)
{
while (comp(m,pct[a[st]])) ++st;
while (comp(pct[a[dr]],m)) --dr;
if (st <= dr) swap(a[st++], a[dr--]);
}
if (st<q) sort(st,q);
if (dr>p) sort(p,dr);
}
long double semn(Punct a, Punct b, Punct c) { return (long double)a.x*b.y + b.x*c.y + a.y*c.x - c.x*b.y - b.x*a.y - c.y*a.x; }
int main()
{
freopen("infasuratoare.in", "r", stdin);
freopen("infasuratoare.out", "w", stdout);
for (scanf("%d\n", &N), i = 1; i<=N; ++i) scanf("%lf %lf\n", &pct[i].x, &pct[i].y);
for (jos = 1, i = 2; i<=N; ++i) if (pct[i].y < pct[jos].y || (pct[i].y == pct[jos].y && pct[i].x < pct[jos].x)) jos = i;
swap(pct[jos],pct[1]);
jos = 1;
for (i = 2; i<=N; ++i) a[i] = i;
sort(2,N);
st[0] = 1;
st[1] = 2
vf = 1;
for (i = 3; i<=N; ++i)
{
while (vf >=2 && semn(pct[a[st[vf-1]]],pct[a[st[vf]]],pct[a[i]]) < 0) vf--;
st[++vf] = i;
}
printf("%d\n", vf+1);
for (i = 0; i<=vf; ++i) printf("%.6lf %.6lf\n", pct[st[a[i]]].x, pct[st[a[i]]].y);
return 0;
}