Pagini recente » Cod sursa (job #2777651) | Cod sursa (job #2465314) | Cod sursa (job #1437324) | Cod sursa (job #2293191) | Cod sursa (job #270299)
Cod sursa(job #270299)
#include <stdio.h>
#include <math.h>
#define Nmax 120001
struct Punct { long double x, y; } pct[Nmax];
int N, i, jos;
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(Punct &a, Punct &b) { Punct tmp = a; a = b; b = tmp; }
void sort(int p, int q)
{
int st = p, dr = q;
Punct m = pct[(st + dr) >> 1];
while (st < dr)
{
while (comp(m,pct[st])) ++st;
while (comp(pct[dr],m)) --dr;
if (st <= dr) swap(pct[st++], pct[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;
sort(2,N);
st[0] = 1;
st[1] = 2;
vf = 1;
for (i = 3; i<=N; ++i)
{
while (vf >=2 && semn(pct[st[vf-1]],pct[st[vf]],pct[i]) < 0) vf--;
st[++vf] = i;
}
printf("%d\n", vf+1);
for (i = 0; i<=vf; ++i) printf("%.6Lf %.6Lf\n", pct[st[i]].x, pct[st[i]].y);
return 0;
}