Cod sursa(job #871055)

Utilizator fhandreiAndrei Hareza fhandrei Data 4 februarie 2013 12:53:19
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.63 kb
// Include
#include <fstream>
#include <iomanip>
#include <vector>
#include <algorithm>
using namespace std;

// Definitii
#define mp make_pair

#define point pair<double,double>
#define y first
#define x second

#define leftTurn(a,b,c) (det(a, b, c)>0)

#define prev at(convexHull.size()-2)
#define top at(convexHull.size()-1)
#define pb push_back
#define popb pop_back

// Constante
const int sz = (int)12e4+1;

// Functii
double det(point a, point b, 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;	}

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

int num;

point points[sz];
point minPoint, current;
vector<point> convexHull;

class byAngle
{
	public:
	bool operator() (point a, point b)
	{	return leftTurn(minPoint, a, b);	}
};

// Main
int main()
{
	out << fixed << setprecision(6);
	in >> num;
	in >> minPoint.x >> minPoint.y;
	
	for(int i=1 ; i<num ; ++i)
	{
		in >> current.x >> current.y;
		if(current < minPoint)
		{
			points[i] = minPoint;
			minPoint = current;
		}
		else
			points[i] = current;
	}
	
	sort(points+1, points+num, byAngle());
	
	convexHull.reserve(num);
	convexHull.pb(minPoint);
	convexHull.pb(points[1]);
	
	for(int i=2 ; i<num ; ++i)
	{
		while(!leftTurn(convexHull.prev, convexHull.top, points[i]))
			convexHull.popb();
		convexHull.pb(points[i]);
	}
	
	out << convexHull.size() << '\n';
	vector<point>::iterator it, end=convexHull.end();
	
	for(it=convexHull.begin() ; it!=end ; ++it)
		out << it->first << ' ' << it->second << '\n';
	
	in.close();
	out.close();
	return 0;
}