Cod sursa(job #270299)

Utilizator coderninuHasna Robert coderninu Data 3 martie 2009 21:21:18
Problema Infasuratoare convexa Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 1.37 kb
#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;
}