Cod sursa(job #2560824)

Utilizator mircearoataMircea Roata Palade mircearoata Data 28 februarie 2020 12:03:38
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.48 kb
#pragma GCC optimize("O3")

#include <fstream>
#include <algorithm>
#include <deque>
#include <iomanip>

using namespace std;

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

int n;
struct point {
	double x, y;
	double slope() {
		if (x == 0 && y == 0)
			return -1e158;
		return y / x;
	}
};
point operator+ (point a, point b) {
	return { a.x + b.x, a.y + b.y };
}
point operator-(point a, point b) {
	return { a.x - b.x, a.y - b.y };
}
ostream& operator<< (ostream& os, point& p) {
	os << '(' << p.x << ',' << p.y << ')';
	return os;
}
bool operator< (const point l, const point r) {
	return l.x == r.x ? l.y < r.y : l.x < r.x;
}

point v[120005];
point firstPoint = { 1e30, 1e30 };

bool isDr(point a, point b, point 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) < 0;
}

int main() {
	in >> n;
	out << fixed << setprecision(6);
	for (int i = 1; i <= n; i++) {
		in >> v[i].x >> v[i].y;
		firstPoint = min(firstPoint, v[i]);
	}
	sort(v + 1, v + n + 1, [](const point& l, const point& r) {
		return (l - firstPoint).slope() < (r - firstPoint).slope();
	});
	deque<point> s;
	s.push_back(v[1]);
	s.push_back(v[2]);
	for (int i = 3; i <= n; i++) {
		while (s.size() >= 2 && isDr(s[s.size() - 2], s[s.size() - 1], v[i])) {
			s.pop_back();
		}
		s.push_back(v[i]);
	}
	out << s.size() << '\n';
	while (!s.empty()) {
		out << s.front().x << ' ' << s.front().y << '\n';
		s.pop_front();
	}
}