Cod sursa(job #2268255)

Utilizator dahaandreiDaha Andrei Codrin dahaandrei Data 24 octombrie 2018 16:57:41
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.04 kb
#include <fstream>
#include <algorithm>
#include <vector>
#include <iomanip>

using namespace std;

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

const int MAXN = 12e4;

int n;
pair<double, double> p;
pair<double, double> Points[MAXN + 1], pol[MAXN + 1];

double det(pair<double, double> a, pair<double, double> b, pair<double, double> c) {
	return (a.first - c.first) * (b.second - c.second) - (a.second - c.second) * (b.first - c.first);
}

bool cmp(pair<double, double> a, pair<double, double> b) {
	return det(Points[0], a, b) > det(Points[0], b, a);
}

int main() {
	in >> n;
	for (int i = 0; i < n; ++ i) {
		in >> p.first >> p.second;
		Points[i] = p;
	}
	sort(Points, Points + n, cmp);

	pol[0] = Points[0];
	pol[1] = Points[1];
	int cur = 2;
	for (int i = 2; i < n; ++ i) {
		while (cur > 1 && det(pol[cur - 2], pol[cur - 1], Points[i]) <= 0) -- cur;
		pol[cur ++] = Points[i];
	}

	out << cur << '\n';
	for (int i = 0; i < cur; ++ i) out << fixed << setprecision(12) << pol[i].first << ' ' << pol[i].second << '\n';

	return 0;
}