Cod sursa(job #1197618)

Utilizator crucerucalinCalin-Cristian Cruceru crucerucalin Data 13 iunie 2014 00:09:36
Problema Infasuratoare convexa Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 2.08 kb
#include <fstream>
#include <algorithm>
#include <vector>
#include <stack>
#include <cmath>

#define NMAX 120005
#define EPS 1.000e-12

using namespace std;


struct Point {
	Point(double _x = 0, double _y = 0) : x(_x), y(_y) {};

	double x;
	double y;
};

Point smallestY;
vector<Point> points;
vector<Point> convexHull;
stack<Point> hull;

/**
 * Se bazeaza pe calculul ariei cu determinantul.
 */
int isClockWise(Point &a, Point &b, Point &c)
{
	double area = (b.x - a.x)*(c.y - a.y) - (b.y - a.y)*(c.x - a.x);

	if (area < 0)
		return -1; // Nu este clockwise
	else if (area > 0)
		return 1;
	else
		return 0; // Sunt coliniare
}

bool yCmp(Point a, Point b)
{
	if (fabs(a.y - b.y) < EPS)
		return false;
	else if (a.y < b.y)
		return true;
	else
		return false;
}

bool slopeCmp(Point a, Point b)
{
	double angle1 = atan2(a.y - smallestY.y, a.x - smallestY.x) * 180 / M_PI;
	double angle2 = atan2(b.y - smallestY.y, b.x - smallestY.x) * 180 / M_PI;

	if (angle1 < 0)
		angle1 = 360.0 + angle1;

	if (angle2 < 0)
		angle2 = 360.0 + angle2;

	if (fabs(angle1 - angle2) < EPS)
		return false;
	else if (angle1 < angle2)
		return true;
	else
		return false;
}

int main()
{
	ifstream fin;
	ofstream fout;

	fin.open("infasuratoare.in");
	fout.open("infasuratoare.out");
	fout.precision(6);
	fout.setf(std::ios::fixed, std::ios::floatfield);


	int N;

	fin >> N;
	for (int i = 0; i < N; ++i) {
		double x, y;
		fin >> x >> y;
		points.push_back(Point(x, y));
	}

	sort(points.begin(), points.end(), yCmp);
	smallestY = points[0];
	sort(points.begin() + 1, points.end(), slopeCmp);

	hull.push(points[0]);
	hull.push(points[1]);

	for (int i = 2; i < N; ++i) {
		Point top = hull.top();
		hull.pop();

		while (isClockWise(hull.top(), top, points[i]) <= 0) {
			top = hull.top();
			hull.pop();
		}

		hull.push(top);
		hull.push(points[i]);
	}

	while (!hull.empty()) {
		Point p = hull.top();
		convexHull.push_back(p);
		hull.pop();
	}

	fout << convexHull.size() << endl;
	for (int i = convexHull.size() - 1; i >= 0; --i)
		fout << convexHull[i].x << " " << convexHull[i].y << endl;

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

	return 0;
}