Cod sursa(job #475745)

Utilizator vlad.maneaVlad Manea vlad.manea Data 8 august 2010 12:21:24
Problema Infasuratoare convexa Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 2.18 kb
#include <fstream>
#include <cmath>
#include <stack>
#include <vector>
#include <algorithm>
#include <iomanip>

#define nmax (120000)
#define EPS (0.0000000000001)
#define PI (3.1415926535897932)

using namespace std;

struct point
{
	double x, y, s;

	point(double x, double y)
	{
		this->x = x;
		this->y = y;
	}

	point()
	{
		x = y = 0;
	}
}; 

vector<point> P;
stack<int> S;
int N;

void read()
{
	double x, y;
	ifstream fin("infasuratoare.in");

	fin >> N;

	for (int i = 0; i < N; ++i)
	{
		fin >> x >> y;
		P.push_back(point(x, y));
	}

	fin.close();
}

inline bool smaller(const double &a, const double &b)
{
	return a < b - EPS;
}

inline bool equal(const double &a, const double &b)
{
	return b - EPS < a && a < b + EPS;
}

inline bool compare(const point &P, const point &Q)
{
	return smaller(P.s, Q.s);
}

inline bool isleft(const point &P0, const point &P1, const point &P2)
{
	return (P1.x - P0.x) * (P2.y - P0.y) - (P2.x - P0.x) * (P1.y - P0.y) > EPS;
}

void solve()
{
	point Q(numeric_limits<double>::max(), numeric_limits<double>::max());

	for (int i = 0; i < N; ++i)
	{
		if (smaller(P[i].x, Q.x) || equal(P[i].x, Q.x) && smaller(P[i].y, Q.y))
		{
			Q = point(P[i].x, P[i].y);
		}
	}

	for (int i = 0; i < N; ++i)
	{
		P[i].s = atan2(Q.y - P[i].y, Q.x - P[i].x);
		P[i].s = (P[i].s < -EPS? P[i].s + 2 * PI: P[i].s);
	}

	sort(P.begin(), P.end(), compare);

	S.push(0);
	S.push(1);

	for (int i = 2; i != 1; i = (i + 1) % N)
	{
		int j, k;
		
		if (S.size() > 1)
		{
			k = S.top();
			S.pop();
			j = S.top();
			S.push(k);
		}

		while (S.size() > 1 && !isleft(P[j], P[k], P[i]))
		{
			S.pop();

			if (S.size() > 1)
			{
				k = S.top();
				S.pop();
				j = S.top();
				S.push(k);
			}
		}

		S.push(i);
	}

	S.pop();
}

void reck(ofstream &fout)
{
	if (S.size() > 0)
	{
		int k = S.top();
		
		S.pop();
		reck(fout);
		fout << setprecision(12) << P[k].x << ' ' << P[k].y << '\n';
	}
}

void write()
{
	ofstream fout("infasuratoare.out");

	fout << S.size() << '\n';
	reck(fout);

	fout.close();
}

int main()
{
	read();
	solve();
	write();
	return 0;
}