Cod sursa(job #445995)

Utilizator voyagerSachelarie Bogdan voyager Data 24 aprilie 2010 18:25:30
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.96 kb
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <algorithm>
#include <stack>
#define FIN "infasuratoare.in"
#define FOUT "infasuratoare.out"
#define FOR(i, n) for(int i = 0; i < n; ++i)
#define FORI(i, v, T) for(T::iterator i = v.begin(); i != v.end(); ++i)
#define INF 1000000000

using namespace std;

typedef pair<double, double> POINT;

vector<POINT > pts;
stack<POINT* > st;

class Sorter
{
	POINT *orig;
public:
	Sorter(POINT *p)
	{
		orig = p;
	}
	static bool left(POINT& p1, POINT& p2, POINT& p3)
	{
		return (long double)(p3.first - p1.first) * (long double)(p2.second - p1.second) <
			   (long double)(p2.first - p1.first) * (long double)(p3.second - p1.second);
	}
	bool operator() (const POINT& p1, const POINT& p2) const
	{
		return (long double)(p1.first - orig->first) * (long double)(p2.second - orig->second) > 
			   (long double)(p2.first - orig->first) * (long double)(p1.second - orig->second);
	}
};

void printStack(stack<POINT* >& st)
{
	if (!st.empty())
	{
		POINT *p = st.top();
		st.pop();
		printStack(st);
		printf("%lf %lf\n", p->first, p->second);
	}
}

int main()
{
	int n, orig;
	POINT origPt(INF, INF);
	FILE *fin = freopen(FIN, "r", stdin), *fout = freopen(FOUT, "w", stdout);
	scanf("%d", &n);
	FOR(i, n)
	{
		double x, y;
		scanf("%lf %lf", &x, &y);
		pts.push_back(make_pair(x, y));
		if (x < origPt.first || x == origPt.first && y < origPt.second)
			origPt.first = x, origPt.second = y, orig = i;
	}
	
	swap(pts[orig], pts[pts.size() - 1]);
	pts.pop_back();
	sort(pts.begin(), pts.end(), Sorter(&origPt));
	st.push(&origPt);
	st.push(&pts[0]);
	st.push(&pts[1]);

	FORI(it, pts, vector<POINT >)
	if (it > pts.begin() + 1)
	{
		POINT *p;
		p = st.top();
		st.pop();
		while (!Sorter::left(*st.top(), *p, *it))
		{
			p = st.top();
			st.pop();
		}
		st.push(p);
		st.push(&(*it));
	}
	
	printf("%d\n", st.size());
	printStack(st);

	fclose(fout);
	return 0;
}