Cod sursa(job #2051366)

Utilizator SlevySlevoaca Stefan-Gabriel Slevy Data 28 octombrie 2017 20:57:49
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.57 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) {

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

		inf.push_back(points[i]);
		sup.push_back(points[i]);
	}

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