Cod sursa(job #399527)

Utilizator alex@ndraAlexandra alex@ndra Data 20 februarie 2010 16:51:04
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.92 kb
#include <fstream>
#include <iomanip.h>
#include <algorithm>
using namespace std;

const int MAX_N = 120010;

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

int n;
punct a[MAX_N];
int s[MAX_N], viz[MAX_N];

int signum(punct a, punct b, punct c)
{
	return 1 - ((a.x - c.x) * (b.y - c.y) - (b.x - c.x) * (a.y - c.y) <= 0);
}

int main()
{
	int i, p;
	ifstream f("infasuratoarea.in");

	ofstream g("infasuratoarea.out");

	f>>n;

	for (i = 1; i <= n; ++i)
		 f>>a[i].x>>a[i].y;

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

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

			viz[s[++s[0]] = i] = 1;
		}
	}

	g<<s[0]-1<<"\n";
	g<<setiosflags(ios::showpoint)<<setprecision(6);

	
	for (i = 1; i < s[0]; ++i)
		g<<a[s[i]].x<<" "<<a[s[i]].y<<"\n";
	
	return 0;
}