Cod sursa(job #2051214)

Utilizator SlevySlevoaca Stefan-Gabriel Slevy Data 28 octombrie 2017 17:35:04
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.79 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <iomanip>

using namespace std;

typedef pair<double, double> point;
vector<point> points;
vector<point> inf, sup;

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

	if (fp.first < sp.first)
		return true;
	if (fp.first == sp.first && fp.second < sp.second)
		return true;
	return false;
}

void read() {

	int n;
	double x, y;

	ifstream in("infasuratoare.in");
	
	for (in >> n; n; --n) {

		in >> 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();
	sort(points.begin(), points.end(), compare);

	point aux;

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

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

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

	for (int i = points.size() - 1; i >= 0; --i) {

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

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

	ofstream out("infasuratoare.out");

	out << inf.size() + sup.size() - 2 << "\n";
	out << setprecision(6) << fixed;
	for (unsigned int i = 0; i < inf.size(); ++i)
		out << inf[i].first << " " << inf[i].second << "\n";

	for (unsigned int i = 1; i < sup.size() - 1; ++i)
		out << sup[i].first << " " << sup[i].second << "\n";
	out << "\n";
	out.close();

	return 0;
}