Cod sursa(job #2040593)

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

using namespace std;

typedef pair<double, double> point;
vector<point> points;
vector<point> sol;
point origin(oo, oo);

void read() {

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

		in >> x >> y;
		if ((origin.first - x > 1e-12) || ((abs(origin.first - x) < 1e-12) && (origin.second - y > 1e-12))) {
			origin = make_pair(x, y);
			pos = i - 1;
		}
		points.push_back(make_pair(x, y));
	}
	swap(points[0], points[pos]);
	in.close();
}

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(origin, fp, sp) > 1e-12)
		return true;
	return false;
}

int main() {

	read();
	sort(points.begin() + 1, 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]) < 1e-12) {

			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;
}