Cod sursa(job #2875233)

Utilizator Langa_bLanga Radu Langa_b Data 21 martie 2022 12:17:18
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.25 kb
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <stack>
#include <vector>
using namespace std;
//ifstream cin("infasuratoare.in");
//ofstream cout("infasuratoare.out");
class point {
public:
	long double x, y;
	long double operator*(point a) {
		return x * a.y - y * a.x;
	}
	point operator-(point a) {
		return { x - a.x, y - a.y };
	}
};
bool cmp(point a, point b) {
	return (a * b < 0);
}
int n;
point v[120002];
int main() {
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> v[i].x >> v[i].y;
	}
	sort(v, v + n, cmp);
	stack<pair<point, point>> st;
	st.push({ v[0], v[1] });
	for (int i = 2; i < n; i++) {
		int ok = 0;
		while (ok == 0) {
			if (st.empty() == 1) {
				ok = 1;
				st.push({ st.top().second , v[i]});
				break;
			}
			point i1 = st.top().second-st.top().first;
			point i2 = v[i] - st.top().first;
			if (i1 * i2 > 0) {
				st.pop();
			}
			else {
				ok = 1;
				st.push({ st.top().second, v[i] });
			}
		}
	}
	vector<point>ans;
	while (st.empty() != 1) {
		ans.emplace_back(st.top().first);
		st.pop();
	}
	cout << ans.size()<<'\n';
	for (int i = 0; i <ans.size(); i++) {
		cout << setprecision(9) << ans[i].x<< ' ' << ans[i].y << fixed << '\n';
	}
}