Cod sursa(job #880226)

Utilizator vlad.maneaVlad Manea vlad.manea Data 16 februarie 2013 15:09:58
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.8 kb
#include <fstream>
#include <iomanip>
#include <limits>
#include <algorithm>
#include <cmath>

using namespace std;

#define Point pair<double, double>
#define InFile "infasuratoare.in"
#define OutFile "infasuratoare.out"
#define NMax 120000
const double Eps = numeric_limits<double>::epsilon();
const int Precision = 13;

int P, H;
Point points[NMax];
Point hull[NMax];

inline double crossProduct(const Point &p0, const Point &p1, const Point &p2)
{
	return (p1.first - p0.first) * (p2.second - p0.second) - (p1.second - p0.second) * (p2.first - p0.first);
}

inline bool minimumCompare(const Point &p1, const Point &p2)
{
	return p1.first + Eps < p2.first || abs(p1.first - p2.first) < Eps && p1.second + Eps < p2.second;
}

inline bool angleCompare(const Point &p1, const Point &p2)
{
	return crossProduct(points[0], p1, p2) > Eps;
}

inline void clear(int p)
{
	while (H >= 2 && crossProduct(hull[H - 2], hull[H - 1], points[p]) + Eps < 0)
	{
		--H;
	}
}

void read()
{
	ifstream fin(InFile);
	fin >> P;
	
	for (int p = 0; p < P; ++p)
	{
		fin >> points[p].first >> points[p].second;
	}

	fin.close();
}

void solve()
{
	// Find minimum
	swap(*min_element(points, points + P, minimumCompare), points[0]);

	// Sort rest of points
	sort(points + 1, points + P, angleCompare);

	// Insert base elements in hull
	hull[H++] = points[0];
	hull[H++] = points[1];

	// Compute convex hull
	for (int p = 2; p < P; ++p)
	{
		clear(p);
		hull[H++] = points[p];
	}
}

void write()
{
	ofstream fout(OutFile);
	fout << H << '\n';	
	fout.setf(ios::fixed, ios::floatfield);
	fout.precision(Precision);

	for (int h = 0; h < H; ++h)
	{
		fout << hull[h].first << ' ' << hull[h].second << '\n';
	}

	fout.close();
}

int main()
{
	read();
	solve();
	write();
}