Cod sursa(job #758129)

Utilizator fhandreiAndrei Hareza fhandrei Data 14 iunie 2012 15:48:17
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.73 kb
//Include
#include <fstream>
#include <iomanip>
#include <utility>
#include <vector>
using namespace std;

//Definitii
#define t_point pair<double, double>
#define y first
#define x second
#define mp make_pair
#define pb push_back
#define top at(convexHull.size()-1)
#define prev at(convexHull.size()-2)
#define pop pop_back
#define leftTurn(a,b,c) (det(a,b,c)>0)

//Functii
double det(t_point a, t_point b, t_point c);

//Variabile
ifstream in("infasuratoare.in");
ofstream out("infasuratoare.out");

int pointsNumber;

t_point minPoint, tempPoint;
vector<t_point> points, convexHull;

//Clase de sortare
class byAngle
{
	public:
	bool operator() (t_point a, t_point b)
	{	return leftTurn(minPoint, a, b);	}
};

//Main
int main()
{
	in >> pointsNumber >> minPoint.x >> minPoint.y;
	points.reserve(pointsNumber);
	convexHull.reserve(pointsNumber);
	out << fixed << setprecision(6);
	
	for(int i=1 ; i< pointsNumber ; ++i)
	{
		in >> tempPoint.x >> tempPoint.y;
		if(tempPoint < minPoint)
		{
			points.pb(minPoint);
			minPoint = tempPoint;
		}
		else
			points.pb(tempPoint);
	}
	
	sort(points.begin(), points.end(), byAngle());
	
	vector<t_point>::iterator it=points.begin(), end=points.end();
	
	convexHull.pb(minPoint);
	convexHull.pb(*it++);
	
	for(; it!=end ; ++it)
	{
		while(!leftTurn(convexHull.prev, convexHull.top, *it))
			convexHull.pop();
		convexHull.pb(*it);
	}
	
	it = convexHull.begin();	end = convexHull.end();
	out << convexHull.size() << '\n';
	for(; it!=end ; ++it)
		out << it->x << ' ' << it->y << '\n';
	
	in.close();
	out.close();
	return 0;
}

double det(t_point a, t_point b, t_point c)
{	return a.x*b.y + b.x*c.y + c.x*a.y - a.y*b.x - b.y*c.x - c.y*a.x;	}