Cod sursa(job #270316)

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