Cod sursa(job #2552949)

Utilizator mircearoataMircea Roata Palade mircearoata Data 21 februarie 2020 13:07:28
Problema Infasuratoare convexa Scor 50
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.7 kb
#define _USE_MATH_DEFINES
#include <iostream>
#include <fstream>
#include <cmath>
#include <algorithm>
#include <deque>
#include <iomanip>

using namespace std;

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

int n;
struct point {
	double x, 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 };

double roll(double low, double high, double increments, double val) {
	if (val < low)
		return roll(low, high, increments, val + increments);
	if (val >= high)
		return roll(low, high, increments, val - increments);
	return val;
}

double atan2deg(double x, double y) {
	if (x == 0 && y == 0)
		return -180;
	return atan2(y, x) * 180 / M_PI;
}

double deg(point a, point b, point c) {
	return roll(0, 360, 360, atan2deg(a.x - b.x, a.y - b.y) - atan2deg(c.x - b.x, c.y - b.y));
}

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 atan2deg(l.x - firstPoint.x, l.y - firstPoint.y) < atan2deg(r.x - firstPoint.x, r.y - firstPoint.y);
	});
	deque<point> s;
	s.push_back(v[1]);
	s.push_back(v[2]);
	for (int i = 3; i <= n; i++) {
		while (s.size() >= 2 && abs(deg(s[s.size() - 2], s[s.size() - 1], v[i])) > 180) {
			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();
	}
}