Cod sursa(job #1584382)

Utilizator AlexandraaaaMereu Alexandra Alexandraaaa Data 30 ianuarie 2016 00:35:01
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.58 kb
#include <iostream>
#include <fstream>
#include <stack>
#include <cmath>
#include <vector>
#include <algorithm>
#include <iomanip>
#define eps 0.000000000000001
#define inf 1000000000

using namespace std;

pair<double, double> O;

bool orient(pair<double, double> a, pair<double, double> b, pair<double, double> c){
	double x, y;
	x = (b.first - a.first) * (c.second - a.second);
	y = (b.second - a.second) * (c.first - a.first);
	return x-y > 0;
}

bool cmp1(pair<double, double> a, pair<double, double> b){
	double x, y;
	x = atan2(a.second - O.second, a.first - O.first);
	y = atan2(b.second - O.second, b.first - O.first);
	return x < y;
}

int main(){
	ifstream f("infasuratoare.in");
	ofstream g("infasuratoare.out");

	int n;
	vector<pair<double, double> > V;

	O = make_pair(inf, inf);

	f >> n;
	int it = 0;
	for (int i = 0; i < n; ++i){
		double x, y;
		f >> x >> y;
		pair<double, double> P(x, y);
		V.push_back(P);

		if (O.first == P.first){
			if (O.second > P.second){
				O = P;
				it = i;
			}
		}
		else
			if (O.first > P.first){
				O = P;
				it = i;
			}
	}

	swap(V[0],V[it]);
	sort(V.begin()+1, V.end(), cmp1);

	stack<pair<double, double> > S;
	S.push(V[0]);

	for (int i = 1; i < V.size() - 1; ++i){
		if (orient(S.top(), V[i], V[i + 1]))
			S.push(V[i]);
	}
	if (orient(S.top(), V[V.size() - 1], O))
		S.push(V[V.size() - 1]);

	g << fixed << setprecision(12) << S.size() << "\n";
	while (!S.empty()){
		g << S.top().first << " " << S.top().second << "\n";
		S.pop();
	}

	f.close();
	g.close();

	return 0;
}