Cod sursa(job #345183)

Utilizator chris_11Botau Cristian chris_11 Data 2 septembrie 2009 00:50:40
Problema Infasuratoare convexa Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 2.08 kb
#include <fstream>
#include <iostream>
#include <iomanip>
#include <stack>
#include <vector>
#include <utility>
#include <algorithm>

#define INPUT_F "infasuratoare.in"
#define OUTPUT_F "infasuratoare.out"

using namespace std;

#define EPS 1E-12
#define MAX_N 10000

typedef pair<double, double> Point;
typedef vector<Point> PV;
#define x first
#define y second

PV a;

inline double abs(double x) { if (x < 0) return -x; return x; }

bool isLeftTurn(Point a, Point b, Point c)
{
	double r = (c.x - a.x)*(b.y - a.y) - (c.y - a.y)*(b.x - a.x);
	
	if (abs(r) < EPS)
		return (c.x - a.x)*(c.x - a.x) + (c.y - a.y)*(c.y - a.y) <
			   (b.x - a.x)*(b.x - a.x) + (b.y - a.y)*(b.y - a.y);

	if (r < 0)
		return true;

	return false;
}

struct PolarCompare
{
	PolarCompare(const Point &b)
	{
		this->base = b;
	}

	bool operator ()(const Point &a, const Point &b)
	{
		return isLeftTurn(base, a, b);
	}

	Point base;
};

void read_data(istream &in)
{
	int N;
	double x, y;
	in >> N;
	for (int i = 0; i < N; ++i)
	{
		in >> x >> y;
		a.push_back(Point(x, y));
	}
}

void print_data(ostream &out, const PV &v)
{
	out << v.size() << endl;
	out.flags(ios::fixed);
	for (PV::const_iterator i = v.begin(); i != v.end(); i++)
		out << setprecision(6) << i->x << " " << i->y << endl;
}

// very inefficient design/implementation all for the sake of clarity
PV solve(PV &a)
{
	swap(a[0], *min_element(a.begin(), a.end()));
	sort(a.begin() + 1, a.end(), PolarCompare(a[0]));
	//print_data(cout, a);
	//int x;
	//cin >> x;

	vector<Point> result;
	result.push_back(a[0]);
	result.push_back(a[1]);

	for (PV::iterator i = a.begin() + 2; i != a.end(); i++)
	{
		while (!isLeftTurn(result.end()[-2], result.end()[-1], *i))
			result.pop_back();

		result.push_back(*i);
	}
	
	sort(result.begin(), result.end(), PolarCompare(Point(0, 0)));
	return result;
}

int main()
{
	ifstream fin(INPUT_F);
	ofstream fout(OUTPUT_F);

	read_data(fin);
	//print_data(cout, a);
	print_data(fout, solve(a));

	fin.close();
	fout.close();

	return 0;
}