Cod sursa(job #709305)

Utilizator feelshiftFeelshift feelshift Data 7 martie 2012 22:41:36
Problema Infasuratoare convexa Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 2.97 kb
// http://infoarena.ro/problema/infasuratoare
#include <fstream>
#include <iomanip>
#include <cmath>
#include <algorithm>
#include <vector>
#include <stack>
using namespace std;

#define x first
#define y second

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

const int MAXSIZE = 120001;
const int oo = 0x3f3f3f3f;

int nrPoints,selectedPoints;
bool onConvexHull[MAXSIZE];
int previousPointOnConvexHull[MAXSIZE];
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) {
		double oneAtan = atan2(one.y - minPoint.y,one.x - minPoint.x);
		double twoAtan = atan2(two.y - minPoint.y,two.x - minPoint.x);

		if(oneAtan != twoAtan)
			return (oneAtan < twoAtan);
		else
			return (dist(minPoint,one) < dist(minPoint,two));
	}
};

int main() {
	in >> nrPoints;

	pair<double,double> point;
	for(int i=1;i<=nrPoints;i++) {
		in >> point.x >> point.y;

		if(point.x < minPoint.x || (point.x == minPoint.x && point.y < minPoint.y))
			minPoint = point;

		points.push_back(point);
	}

	//out << "Initial point: " << minPoint.x << " " << minPoint.y << "\n";

	sort(points.begin(),points.end(),compare());

	selectedPoints = 2;

	int previous = find(points.begin(),points.end(),minPoint) - points.begin(),current = 0;
	onConvexHull[previous] = onConvexHull[current] = true;
	previousPointOnConvexHull[current] = previous;

	for(int i=1;i<nrPoints;i++) {
		while(!leftTurn(points[previous],points[current],points[i])) {
			onConvexHull[current] = false;
			current = previous;
			previous = previousPointOnConvexHull[previous];
			selectedPoints--;
		}

		onConvexHull[i] = true;
		previous = current;
		current = i;
		previousPointOnConvexHull[current] = previous;
		selectedPoints++;
	}

	/*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 << selectedPoints << fixed << setprecision(6) << "\n";

	out << minPoint.x << " " << minPoint.y << "\n";
	for(int i=0;i<nrPoints;i++)
		if(onConvexHull[i])
			out << points[i].x << " " << points[i].y << "\n";

	return (0);
}

double dist(pair<double,double> one,pair<double,double> two) {
	return (sqrt(pow(one.x - two.x,2) + pow(one.y - two.y,2)));
}

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);
}