Cod sursa(job #2223403)

Utilizator oldatlantianSerban Cercelescu oldatlantian Data 20 iulie 2018 08:22:16
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.25 kb
/// Graham
#include <bits/stdc++.h>
#define x first
#define y second
#define rev(v) (v.rbegin())
using namespace std;

ifstream fi("infasuratoare.in");
ofstream fo("infasuratoare.out");

using f64 = double;
using ptx = pair<f64, f64>;

const f64 EPS = 1e-12;


vector<ptx> v, hull;
int n;


static f64 det(const ptx &c, const ptx &a, const ptx &b) {
	return (a.x - c.x) * (b.y - c.y) - (a.y - c.y) * (b.x - c.x); }

static int orient(const ptx &c, const ptx &b, const ptx &a) {
	f64 d = det(c, a, b);
	if (abs(d) < EPS)
		return 0;
	return d > 0 ? 1 : -1; }

static f64 norm(const ptx &a, const ptx &b) {
	return (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y); }


int main() {
	fi >> n;
	v.resize(n);
	hull.reserve(n);

	for (auto &i: v)
		fi >> i.x >> i.y;
	

	swap(*min_element(begin(v), end(v)), v[0]);
	hull.push_back(v[0]);

	sort(begin(v) + 1, end(v), [&](const ptx &a, const ptx &b) {
		return orient(v[0], a, b) == 0 ? norm(v[0], a) < norm(v[0], b) : orient(v[0], a, b) < 0; });

	for (int i = 1; i < n; ++i) {
		while (hull.size() > 2 && orient(rev(hull)[0], rev(hull)[1], v[i]) <= 0)
			hull.pop_back();
		hull.push_back(v[i]); }

	fo << setprecision(6) << fixed;
	fo << hull.size() << '\n';
	for (auto i: hull)
		fo << i.x << ' ' << i.y << '\n';

	return 0; }