Cod sursa(job #2875289)

Utilizator Langa_bLanga Radu Langa_b Data 21 martie 2022 13:10:03
Problema Infasuratoare convexa Scor 60
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.36 kb
#include <fstream>
#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 };
	}
};
point v[120002];
bool cmp(point a, point b) {
	return ((a-v[0]) * (b-v[0]) < 0);
}
int n;
int main() {
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> v[i].x >> v[i].y;
	}
	sort(v + 1, 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;
	int cnt = 1;
	while (st.empty() != 1) {
		if (cnt == 1) {
			ans.push_back(st.top().second);
			cnt++;
		}
		ans.emplace_back(st.top().first);
		st.pop();
	}
	cout << ans.size() << '\n';
	cout << setprecision(9) << fixed;
	for (int i = 0; i < ans.size(); i++) {
		cout << ans[i].x << ' ' << ans[i].y << '\n';
	}
}