Cod sursa(job #2720556)

Utilizator gavra_bogdanBogdan Gavra gavra_bogdan Data 10 martie 2021 22:57:40
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1 kb
#include <fstream>
#include <vector>
#include <iomanip>
#include <algorithm>

#define ld long double
#define pi std::pair<ld, ld>

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

const ld eps = 1e-12;

ld cross(pi a, pi b, pi c) {
	return (c.second * (b.first-a.first) - c.first * (b.second-a.second) + b.second*a.first - b.first*a.second < eps);
}

int main() {
	int n, dir = 1;
	fin>>n;
	std::vector<pi>vec(n);
	std::vector<int> hull = {0, 1}, viz(n, 0);
	for(int i=0;i<n;i++) fin>>vec[i].second>>vec[i].first;
	std::sort(vec.begin(), vec.end());
	viz[1] = 1;
	for(int i=2;i>=0;i+=dir) if(!viz[i]){
		while(hull.size()>=2 and !cross(vec[hull[hull.size()-2]], vec[hull.back()], vec[i])) viz[hull.back()] = 0, hull.pop_back();
		hull.push_back(i), viz[hull.back()] = 1;
		if(hull.back() == n - 1) dir = -1;
	}
	hull.pop_back();
	fout<<hull.size()<<'\n';
	for(int ind:hull) fout<<std::fixed<<std::setprecision(12)<<vec[ind].second<<" "<<vec[ind].first<<'\n';
}