Cod sursa(job #3173678)

Utilizator RolandPetreanPetrean Roland RolandPetrean Data 23 noiembrie 2023 15:48:19
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.28 kb
#include <bits/stdc++.h>
using namespace std;

struct Point {
	double x, y;
	bool operator<(Point b) const {
		if (x == b.x) return y < b.y;
		return x < b.x;
	}
};
vector<Point> points;

double dist(Point a, Point b) {
	double dx = a.x - b.x, dy = a.y - b.y;
	return dx * dx + dy * dy;
}
double cross(Point a, Point b, Point o = {0, 0}) {
	return (a.x - o.x) * (b.y - o.y) - (a.y - o.y) * (b.x - o.x);
}
bool up(Point p) {
	return p.y > 0 || (p.y == 0 && p.x >= 0);
}
bool cmp(Point a, Point b) {
	Point o = points[0];
	if (up(a) != up(b)) return up(a) < up(b);
	if (cross(a, b) == 0) return dist(o, a) < dist(o, b);
	return cross(a, b) < 0;
}

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

	int n;
	cin >> n;

	points.assign(n, {});
	for (int i = 0; i < n; ++i) {
		cin >> points[i].x >> points[i].y;
		if (points[i] < points[0]) swap(points[i], points[0]);
	}
	sort(points.begin() + 1, points.end(), cmp);

	auto bad = [&](Point a, Point b, Point c) {
		return cross(a, b, c) >= 0;
	};

	vector<Point> st;
	for (int i = 0; i < n; ++i) {
		while (st.size() > 1 && bad(st.end()[-2], st.back(), points[i])) st.pop_back();
		st.push_back(points[i]);
	}

	reverse(st.begin(), st.end());
	for (Point p : st) cout << fixed << setprecision(13) << p.x << " " << p.y << endl;
}