Cod sursa(job #2051287)

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

using namespace std;

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

void read() {

	int n;
	double x, y;

	ifstream in("infasuratoare.in");

	for (in >> n; n; --n) {

		in >> x >> y;
		if (x < origin.first || (x == origin.first && y < origin.second))
			origin = make_pair(x, y);
		points.push_back(make_pair(x, y));
	}

	in.close();
}

inline double cross_product(const point& p, const point& q, const point& r) {

	return (q.first - p.first) * (r.second - p.second) - (r.first - p.first) * (q.second - p.second);
}

int main() {

	read();
	
	sol.push_back(origin);
	point aux(oo, oo), current = sol.back();

	do {
		
		current = sol.back();
		aux = make_pair(oo, oo);
		for (unsigned int i = 0; i < points.size(); i++) {

			if (aux == point(oo, oo) && points[i] != current)
				aux = points[i];
			else if (current != points[i] && cross_product(current, aux, points[i]) < 0)
				aux = points[i];
		}

		sol.push_back(aux);

	} while (sol.front() != sol.back());

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

	return 0;
}