Cod sursa(job #1584404)

Utilizator AlexandraaaaMereu Alexandra Alexandraaaa Data 30 ianuarie 2016 01:39:30
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.46 kb
#include <iostream>
#include <fstream>
#include <stack>
#include <cmath>
#include <vector>
#include <algorithm>
#include <iomanip>
#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){
	return (orient(O, a, b) > 0);
}

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