Cod sursa(job #1584402)

Utilizator AlexandraaaaMereu Alexandra Alexandraaaa Data 30 ianuarie 2016 01:28:16
Problema Infasuratoare convexa Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 1.59 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;

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

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

	vector<pair<double, double> > S;
	S.push_back(V[0]);
	S.push_back(V[1]);

	for (int i = 2; i < V.size(); ++i){
		while (S.size() >= 2 && orient(S[S.size() - 2], S[S.size() - 1], V[i]) <= 0)
			S.pop_back();
		S.push_back(V[i]);
	}

	g << fixed << setprecision(12) << S.size() << "\n";
	for (int i = 0; i <= S.size() - 1; ++i)
		g << S[i].first << " " << S[i].second << "\n";

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

	return 0;
}