Cod sursa(job #1947096)

Utilizator preda.andreiPreda Andrei preda.andrei Data 30 martie 2017 19:01:46
Problema Infasuratoare convexa Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 1.69 kb
#include <cmath>
#include <algorithm>
#include <fstream>
#include <iomanip>
#include <vector>

using namespace std;

const double kEps = 1e-12;
const double kInf = 1e12;

struct Point
{
	double x, y;

	bool operator==(const Point &p) const
	{
		return (x == p.x) && (y == p.y);
	}
};

inline bool Smaller(double a, double b)
{
	return (a - b) < kEps;
}

inline bool Equal(double a, double b)
{
	return abs(a - b) <= kEps;
}

bool CounterClock(const Point &a, const Point &b, const Point &c)
{
	double delta = a.x * (b.y - c.y) + b.x * (c.y - a.y) + c.x * (a.y - b.y);
	return delta > 0;
}

vector<Point> ConvexHull(vector<Point> &vec)
{
	Point left = {kInf, kInf};
	for (const auto &p : vec) {
		if (Smaller(p.x, left.x) || 
			(Equal(p.x, left.x) && Smaller(p.y, left.y))) {
			left = p;
		}
	}

	auto cmp = [left](const Point &a, const Point &b) -> bool {
		if (a == left) {
			return true;
		}
		if (b == left) {
			return false;
		}
		return CounterClock(left, a, b);
	};
	sort(vec.begin(), vec.end(), cmp);

	vector<Point> hull(2);
	hull[0] = vec[0];
	hull[1] = vec[1];

	Point second = hull[0];
	for (unsigned i = 2; i < vec.size(); ++i) {
		while (hull.size() > 2 && !CounterClock(second, hull.back(), vec[i])) {
			hull.pop_back();
			second = hull[hull.size() - 2];
		}
		second = hull.back();
		hull.push_back(vec[i]);
	}
	return hull;
}

int main()
{
	ifstream fin("infasuratoare.in");
	ofstream fout("infasuratoare.out");

	int n;
	fin >> n;

	vector<Point> points(n);
	for (int i = 0; i < n; ++i) {
		fin >> points[i].x >> points[i].y;
	}

	auto hull = ConvexHull(points);
	fout << hull.size() << "\n";
	for (const auto &point : hull) {
		fout << setprecision(13) << point.x << " " << point.y << "\n";
	}

	return 0;
}