Cod sursa(job #2268220)

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

using namespace std;

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

int n;
vector<pair<double, double> > Points;
pair<double, double> p;

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 = 1; i <= n; ++ i) {
		in >> p.first >> p.second;
		Points.push_back(p);
	}
	sort(Points.begin(), Points.end(), cmp);

	vector<pair<double, double> > pol;
	pol.push_back(Points[0]);
	pol.push_back(Points[1]);

	for (int i = 2; i < Points.size(); ++ i) {
		if (det(pol[pol.size() - 2], pol[pol.size() - 1], Points[i]) <= 0) pol.pop_back();
		pol.push_back(Points[i]);
	}

	out << pol.size() << '\n';
	for (auto x : pol) out << fixed << setprecision(12) << x.first << ' ' << x.second << '\n';

	return 0;
}