Cod sursa(job #2040605)

Utilizator SlevySlevoaca Stefan-Gabriel Slevy Data 16 octombrie 2017 00:45:23
Problema Infasuratoare convexa Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 1.53 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <iomanip>
#define oo (1 << 30)
#define EPS 1e-12

using namespace std;

typedef pair<double, double> point;
vector<point> points;
vector<point> sol;
point barycenter(0, 0);

void read() {

	int n;
	double x, y;
	ifstream in("infasuratoare.in");
	in >> n;
	for (int i = 1; i <= n; i++) {

		in >> x >> y;
		barycenter.first += x;
		barycenter.second += y;
		points.push_back(make_pair(x, y));
	}
	in.close();
	barycenter.first /= n;
	barycenter.second /= n;
}

inline double cross_product(const point& origin, const point& fp, const point& sp) {

	return (fp.first - origin.first) * (sp.second - origin.second) - (fp.second - origin.second) * (sp.first - origin.first);
}

bool compare_points(const point& fp, const point& sp) {

	if (cross_product(barycenter, fp, sp) > EPS)
		return true;
	return false;
}

int main() {

	read();
	sort(points.begin(), points.end(), compare_points);
	point aux;

	for (unsigned int i = 0; i < points.size(); i++) {

		sol.push_back(points[i]);
		
		while (sol.size() > 2 && cross_product(sol[sol.size() - 3], sol[sol.size() - 2], sol[sol.size() - 1]) < EPS) {

			aux = sol.back();
			sol.pop_back();
			sol.pop_back();
			sol.push_back(aux);
		}
	}

	ofstream out("infasuratoare.out");
	out << sol.size() << "\n";
	out << setprecision(6) << fixed;
	for (unsigned int i = 0; i < sol.size(); i++)
		out << sol[i].first << " " << sol[i].second << "\n";
	out.close();

	return 0;
}