Cod sursa(job #418073)

Utilizator Binary_FireFlorin Pogocsan Binary_Fire Data 15 martie 2010 13:17:20
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.34 kb
#include <fstream>
#include <vector>
#include <algorithm>
#include <iomanip>

using namespace std;

#define EPS 0.000000000001
#define X first
#define Y second

typedef pair<double,double> dot;

int N, ind;
vector<dot> v;
vector<dot> stack;
dot p0;

bool cmp(dot a, dot b)
{
	return (a.X - p0.X) * (b.Y - p0.Y) < (a.Y - p0.Y) * (b.X - p0.X);
}

double absf(double a) {
	if ( a < 0 ) a *= -1;
	return a;
}

double det(dot a, dot b, dot p) {
	return (a.X - p.X) * (b.Y - p.Y) - (a.Y - p.Y) * (b.X - p.X);
}

int main()
{
	ifstream f("infasuratoare.in");
	ofstream f2("infasuratoare.out");
	
	f >> N;
	for ( int i = 0; i < N; ++i )
	{
		double dotX, dotY;

		f >> dotX >> dotY;
		v.push_back(make_pair(dotX,dotY));
	}
	
	p0 = v[0];
	for ( int i = 0; i < N; ++i )
		if ( v[i].X < p0.X || ( absf(v[i].X - p0.X) < EPS && v[i].Y < p0.Y ) )
		{
			p0 = v[i];
			ind = i;
		}
	swap(v[v.size()-1], v[ind]);
	sort(v.begin(), v.end() - 1, cmp);

	stack.push_back(p0);
	for ( int i = 0; i < v.size() - 1; ++i )
	{
		while ( stack.size() > 1 && det(v[i], stack[stack.size() - 2], stack[stack.size() - 1]) > 0 )
			stack.pop_back();
		stack.push_back(v[i]);
	}

	f2 << stack.size() << "\n";
	for ( int i = 0; i < stack.size(); ++i )
		f2 << fixed << setprecision(6) << stack[i].X << " " << stack[i].Y << endl;

	return 0;
}