Cod sursa(job #1852079)

Utilizator pas.andreiPopovici Andrei-Sorin pas.andrei Data 20 ianuarie 2017 15:44:42
Problema Infasuratoare convexa Scor 90
Compilator cpp Status done
Runda Arhiva educationala Marime 1.17 kb
#include <fstream>
#include <vector>
#include <iomanip>
#include <algorithm>
#define NMAX 120005

using namespace std;

typedef pair<double, double> pii;

ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");

pii v[NMAX];
vector<pii> infasuratoare;

inline double unghi(pii a, pii b, pii c) {
	return a.first*b.second+b.first*c.second+c.first*a.second -b.second*c.first-c.second*a.first-a.second*b.first;
}

int main() {
	int n,i;

	fin>>n;
	for(i=1;i<=n;++i) fin>>v[i].first>>v[i].second;

	sort(v+1,v+n+1);
	infasuratoare.push_back(v[1]);
	infasuratoare.push_back(v[2]);
	for(i=3;i<=n;++i) {
		while(infasuratoare.size()>1 && unghi(infasuratoare[infasuratoare.size()-2],infasuratoare.back(),v[i])<0)
			infasuratoare.pop_back();
		infasuratoare.push_back(v[i]);
	}

	for(i=n-1;i>0;--i) {
		while(infasuratoare.size()>1 && unghi(infasuratoare[infasuratoare.size()-2],infasuratoare.back(),v[i])<0)
			infasuratoare.pop_back();
		infasuratoare.push_back(v[i]);
	}

	infasuratoare.pop_back();
	fout<<infasuratoare.size()<<'\n';
	for(auto it:infasuratoare)
		fout<<fixed<<setprecision(12)<<it.first<<' '<<it.second<<'\n';

	return 0;
}