Cod sursa(job #2744456)

Utilizator gavra_bogdanBogdan Gavra gavra_bogdan Data 24 aprilie 2021 18:39:40
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.93 kb
#include <iostream>
#include <algorithm>
#include <iomanip>
#define ld long double
#define pi std::pair<ld, ld>
#define x first
#define y second

const int N = 1e5 + 5;
const ld eps = 1e-12;

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

pi v[N];
std::vector<int>hull;
bool viz[N];

ld cp(pi a, pi b, pi c) {
	return (a.x*b.y+b.x*c.y+c.x*a.y-a.y*b.x-b.y*c.x-c.y*a.x < eps);
}

int main() {
	int n, dir = 1;
	fin>>n;
	for(int i=1;i<=n;i++) 
		fin>>v[i].y>>v[i].x;
	std::sort(v+1, v+n+1);
	hull.push_back(1), hull.push_back(2), viz[2] = true;
	for(int i=3;i;i+=dir) {
		while(hull.size()>=2 and !cp(v[hull[hull.size()-2]], v[hull.back()], v[i])) viz[hull.back()] = false, hull.pop_back();
		hull.push_back(i), viz[i] = true;
		if(i==n) dir=-1;
	}
	hull.pop_back();
	fout<<hull.size()<<"\n";
	for(int i:hull) fout<<std::fixed<<" "<<std::setprecision(12)<<v[i].y<<" "<<v[i].x<<"\n";
}