Cod sursa(job #3039437)

Utilizator game_difficultyCalin Crangus game_difficulty Data 28 martie 2023 16:09:43
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.15 kb
#include <fstream>
#include <vector>
#include <iomanip>
#include <algorithm>
#include <cmath>

using namespace std;

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

const double PI = 3.14159265358979323846;
using point = pair<double, double>;

bool cmp(const point& a, const point& b) {
	if (a.first >= 0 && b.first >= 0) {
		return a.second * b.first < b.second* a.first;
	}
	else if (a.first <= 0 && b.first >= 0) return 0;
	else if (a.first >= 0 && b.first <= 0) return 1;
	else {
		return a.second * b.first < b.second* a.first;
	}
}

int main() {
	int n;
	cin >> n;
	vector<point> v;
	point o = { -1, -1 };
	for (int i = 1; i <= n; i++) {
		double x, y;
		cin >> x >> y;
		v.push_back({ x, y });
		if (o == point{-1, -1}) o = { x, y };
		else if (o.second > y) {
			o = { x, y };
		}
		else if (o.second == y && o.first > x) {
			o = { x, y };
		}
	}
	for (point& p : v) {
		p.first -= o.first;
		p.second -= o.second;
	}
	sort(v.begin(), v.end(), cmp);
	cout << setprecision(12) << fixed;
	//for (const point& p : v) {
	//	cout << p.first + o.first << ' ' << p.second + o.second << '\n';
	//}
	vector<int> s{};
	s.push_back(0);
	for (int i = 1; i < n; i++) {
		if (s.size() < 2) {
			s.push_back(i);
		}
		else {
			while (s.size() >= 2) {
				point p1 = v[s[s.size() - 2]];
				point p2 = v[s[s.size() - 1]];
				point p3 = v[i];
				p1.first -= p2.first; p3.first -= p2.first;
				p1.second -= p2.second; p3.second -= p2.second;
				double a1;
				if (p1.first == 0) {
					if (p1.second > 0) a1 = PI / 2;
					else if (p1.second < 0) a1 = 3 * PI / 2;
				}
				else a1 = atan(p1.second / p1.first) + (p1.first < 0 ? PI : 0);
				double a3;
				if (p3.first == 0) {
					if (p3.second > 0) a3 = PI / 2;
					else if (p3.second < 0) a3 = 3 * PI / 2;
				}
				else a3 = atan(p3.second / p3.first) + (p3.first < 0 ? PI : 0);
				if (a1 - a3 + (a1 - a3 < 0 ? 2 * PI : 0) < PI) {
					s.push_back(i);
					break;
				}
				else s.pop_back();
			}
		}
	}
	cout << s.size() << '\n';
	for (int i : s) {
		cout << v[i].first + o.first << ' ' << v[i].second + o.second << '\n';
	}
	return 0;
}