Cod sursa(job #3349260)

Utilizator livliviLivia Magureanu livlivi Data 26 martie 2026 22:02:41
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.33 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <iomanip>

using namespace std;

using T = double;

const T EPS = 1e-15;

int sgn(T x) {
	return (x >= -EPS) - (x <= EPS);
}

struct Point {
	T x, y;

	bool operator<(const Point& rhs) const {
		if (abs(x - rhs.x) < EPS) {
			return y < rhs.y;
		} else {
			return x < rhs.x;
		}
	}
};

T area(Point a, Point b, Point c) {
	return a.x * b.y - a.x * c.y + b.x * c.y - b.x * a.y + c.x * a.y - c.x * b.y;
}

vector<Point> half_envelope(vector<Point>& points, int which_half) {
	vector<Point> env;
	for (auto& p : points) {
		while (env.size() >= 2 
			&& sgn(area(env[env.size() - 2], env[env.size() - 1], p)) == which_half) {
			env.pop_back();
		}
		env.push_back(p);
	}

	return env;
}

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

	int n; cin >> n;

	vector<Point> v(n);
	for (int i = 0; i < n; i++) {
		cin >> v[i].x >> v[i].y;
	}

	sort(v.begin(), v.end());

	vector<Point> upper = half_envelope(v, -1);

	vector<Point> lower = half_envelope(v, 1);
	lower.pop_back();
	reverse(lower.begin(), lower.end());
	lower.pop_back();

	upper.insert(upper.end(), lower.begin(), lower.end());

	cout << upper.size() << "\n";
	cout << fixed << setprecision(14);
	for (auto& p : upper) {
		cout << p.x << " " << p.y << "\n";
	}
	return 0;
}