Cod sursa(job #475750)

Utilizator vlad.maneaVlad Manea vlad.manea Data 8 august 2010 12:54:59
Problema Infasuratoare convexa Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 2.07 kb
#include <cstdio>
#include <cmath>
#include <stack>
#include <vector>
#include <algorithm>
#include <iomanip>

#define nmax (120000)
#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;
vector<int> W;
stack<int> S;
int N;

void read()
{
	double x, y;
	freopen("infasuratoare.in", "r", stdin);
	scanf("%d", &N);

	for (int i = 0; i < N; ++i)
	{
		scanf("%lf%lf", &x, &y);
		P.push_back(point(x, y));
	}
}

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

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 smaller((P2.x - P0.x) * (P1.y - P0.y), (P1.x - P0.x) * (P2.y - P0.y));
}

void solve()
{
	point Q(P[0].x, P[0].y);

	for (int i = 1; i < N; ++i)
	{
		if (smaller(P[i].x, Q.x) || !smaller(P[i].x, Q.x) && !smaller(Q.x, P[i].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 < 0? P[i].s + 2 * PI: P[i].s);
	}

	stable_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 write()
{
	freopen("infasuratoare.out", "w", stdout);
	printf("%d\n", S.size());

	while (S.size() > 0)
	{
		W.push_back(S.top());
		S.pop();
	}

	reverse(W.begin(), W.end());

	for (vector<int>::iterator i = W.begin(); i != W.end(); ++i)
	{
		printf("%lf %lf\n", P[*i].x, P[*i].y);
	}
}

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