Cod sursa(job #2829537)

Utilizator cezar_titianuTitianu Cezar cezar_titianu Data 8 ianuarie 2022 18:30:02
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.49 kb
#include <fstream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <iomanip>

class point {
public:
	double x, y;
	point operator-=(point to_sub) {
		x -= to_sub.x;
		y -= to_sub.y;
		return *this;
	}
	point operator-(point to_sub) {
		point copy = { x, y };
		copy -= to_sub;
		return copy;
	}
};

#define PREC 1e-12
bool Equal(double nr1, double nr2) {
	return std::abs(nr1 - nr2) < PREC;
}

bool CartComp(point pt1, point pt2) {
	return (Equal(pt1.x, pt2.x) ? (PREC < pt2.y - pt1.y) : (PREC < pt2.x - pt1.x));
}
bool RadComp(point pt1, point pt2) {
	return pt1.x * pt2.y > pt1.y * pt2.x;
}

point vec[120005];

int main() {
	std::ifstream fin("infasuratoare.in");
	std::ofstream fout("infasuratoare.out");
	int nrn;
	point first;
	std::vector <point> wrap;
	fin >> nrn;
	for (int index = 0; index < nrn; index++) {
		fin >> vec[index].x >> vec[index].y;
	}
	std::sort(vec, vec + nrn, CartComp);
	first = vec[0];
	for (int index = 0; index < nrn; index++) {
		vec[index].x -= first.x;
		vec[index].y -= first.y;
	}
	std::sort(vec, vec + nrn, RadComp);
	wrap.push_back(vec[0]);
	for (int index = 1; index < nrn; index++) {
		while (wrap.size() > 1 && !RadComp(wrap.back() - wrap[wrap.size() - 2], vec[index] - wrap.back())) {
			wrap.pop_back();
		}
		wrap.push_back(vec[index]);
	}
	fout << wrap.size() << '\n';
	for (const point& now : wrap) {
		fout << std::fixed << std::setprecision(6) << now.x + first.x << ' ' << now.y + first.y << '\n';
	}
}