Cod sursa(job #709505)

Utilizator feelshiftFeelshift feelshift Data 8 martie 2012 10:34:12
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 2.35 kb
// http://infoarena.ro/problema/infasuratoare
#include <fstream>
#include <iomanip>
#include <cmath>
#include <algorithm>
#include <vector>
using namespace std;

#define x first
#define y second

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

const int oo = 0x3f3f3f3f;

int nrPoints;
pair<double,double> minPoint = make_pair(oo,oo);
vector< pair<double,double> > points,convexHull;

double dist(pair<double,double> one,pair<double,double> two);
bool leftTurn(pair<double,double> one,pair<double,double> two,pair<double,double> three);
double determinant(pair<double,double> one,pair<double,double> two,pair<double,double> three);

class compare {
public:
	bool operator() (pair<double,double> one,pair<double,double> two) {
		return (leftTurn(minPoint,one,two));
	}
};

int main() {
	in >> nrPoints;
	points.reserve(nrPoints);

	pair<double,double> point;
	for(int i=1;i<=nrPoints;i++) {
		in >> point.x >> point.y;
		
		// retinem punctul cu abscisa minima,
		// iar in caz de egalitate cu ordonata minima
		minPoint = min(minPoint,point);
		
		
		points.push_back(point);
	}
	
	// stergem punctul minim
	points.erase(find(points.begin(),points.end(),minPoint));
	
	// sortam punctele trigonometric dupa punctul de minim
	sort(points.begin(),points.end(),compare());
	
	// punctul de minim este sigur pe infasuratoarea convexa
	convexHull.push_back(minPoint);
	
	// la fel si urmatorul
	convexHull.push_back(points.front());
	
	//points.insert(points.begin(),minPoint);	

	for(int i=2;i<nrPoints;i++) {
		while(!leftTurn(convexHull[convexHull.size()-2],convexHull[convexHull.size()-1],points[i]))
			convexHull.pop_back();
		convexHull.push_back(points[i]);
	}

	/*for(unsigned int i=0;i<points.size();i++)
		out << points[i].x << " " << points[i].y << "\n";
	out << "\n\n";*/

	//out << "Convex hull:\n";
	out << convexHull.size() << fixed << setprecision(6) << "\n";
	for(unsigned int i=0;i<convexHull.size();i++)
		out << convexHull[i].x << " " << convexHull[i].y << "\n";
	//out << "\n";

	return (0);
}

bool leftTurn(pair<double,double> one,pair<double,double> two,pair<double,double> three) {
	return (determinant(one,two,three) > 0);
}

double determinant(pair<double,double> one,pair<double,double> two,pair<double,double> three) {
	return (one.x * two.y + three.x * one.y + two.x * three.y
		- three.x * two.y - one.x * three.y - two.x * one.y);
}