Cod sursa(job #880197)

Utilizator vlad.maneaVlad Manea vlad.manea Data 16 februarie 2013 14:41:29
Problema Infasuratoare convexa Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 1.72 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

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 < p2.first || p1.first == p2.first && p1.second < p2.second;
}

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

inline void clear(int p)
{
	while (H >= 2 && crossProduct(hull[H - 2], hull[H - 1], points[p]) < 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';

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

	fout << setprecision(12) << hull[0].first << ' ' << hull[0].second << '\n';
	fout.close();
}

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