Cod sursa(job #3173705)

Utilizator RolandPetreanPetrean Roland RolandPetrean Data 23 noiembrie 2023 16:16:11
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.2 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;
	}
	bool operator==(Point b) const {
		return x == b.x && y == b.y;
	}
};
vector<Point> points;

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);
}
double area(Point a, Point b, Point c) {
	return (a.x*(b.y-c.y)+b.x*(c.y-a.y)+c.x*(a.y-b.y));
}
bool cmp(Point a, Point b) {
	return area(points[0], 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 area(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());
	cout << st.size() << endl;
	for (Point p : st) cout << fixed << setprecision(13) << p.x << " " << p.y << endl;
}