Cod sursa(job #383912)

Utilizator raduzerRadu Zernoveanu raduzer Data 18 ianuarie 2010 18:37:52
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.85 kb
#include <cstdio>
#include <algorithm>
using namespace std;

#define pdd pair<double, double>
#define x first
#define y second

const int MAX_N = 120010;

int n, z;
pdd a[MAX_N];
int f[MAX_N], s[MAX_N];

inline int sign(pdd a, pdd b, pdd c)
{
	return (a.x - c.x) * (b.y - c.y) - (b.x - c.x) * (a.y - c.y) > 0;
}

int main()
{
	int i, p;

	freopen("infasuratoare.in", "r", stdin);
	freopen("infasuratoare.out", "w", stdout);

	scanf("%d", &n);

	for (i = 1; i <= n; ++i)
		scanf("%lf %lf", &a[i].x, &a[i].y);

	sort(a + 1, a + n + 1);

	s[z = 1] = 1;

	for (i = 2, p = 1; i; i += (p = (i == n) ? -p : p))
		if (!f[i])
		{
			while (z > 1 && sign(a[i], a[s[z]], a[s[z - 1]]))
				f[s[z--]] = 0;
			f[s[++z] = i] = 1;
		}

	printf("%d\n", z - 1);

	for (i = 1; i < z; ++i)
		printf("%.6lf %.6lf\n", a[s[i]].x, a[s[i]].y);

}