Mai intai trebuie sa te autentifici.

Cod sursa(job #1853176)

Utilizator pas.andreiPopovici Andrei-Sorin pas.andrei Data 21 ianuarie 2017 14:55:55
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.19 kb
#include <fstream>
#include <vector>
#include <iomanip>
#include <algorithm>
#define NMAX 120005

using namespace std;

typedef pair<long double, long double> pii;

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

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

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

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