Cod sursa(job #1197622)

Utilizator crucerucalinCalin-Cristian Cruceru crucerucalin Data 13 iunie 2014 01:01:02
Problema Infasuratoare convexa Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.46 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) {};

	bool operator<( const Point &other ) const
	{
		return x < other.x || y < other.y;
	}

	double x;
	double y;
};

Point points[NMAX];
Point hull[NMAX];


/**
 * Se bazeaza pe calculul ariei cu determinantul.
 */
double clockWiseDet(Point &a, Point &b, Point &c)
{
	return (b.x - a.x)*(c.y - a.y) - (b.y - a.y)*(c.x - a.x);
}

bool clockWiseCmp(Point a, Point b)
{
	return clockWiseDet(points[0], a, b) < 0;
}

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;
	int head;

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

	int pos = 0;
	for (int i = 1; i < N; ++i)
		if (points[i] < points[pos])
			pos = i;
	swap(points[0], points[pos]);
	sort(points + 1, points + N, clockWiseCmp);

	hull[0] = points[0];
	hull[1] = points[1];
	head = 2;

	for (int i = 2; i < N; ++i) {
		while (head >= 2 &&
		       clockWiseDet(hull[head - 2], hull[head - 1], points[i]) > 0) {
			--head;
		}
		hull[head++] = points[i];
	}

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

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

	return 0;
}