Cod sursa(job #3359639)

Utilizator iustinola16Olariu Iustin iustinola16 Data 1 iulie 2026 10:00:39
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.31 kb
#include <algorithm>
#include <fstream>
#include <iomanip>
#include <iostream>
#include <vector>
#define ld long double

using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");

const int NMAX = 12e4 + 5;

struct Point {
	ld x, y;
};

Point o = {0.0, 0.0};

ld dist(Point a, Point b) {
	return (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y);
}

ld crossproduct(Point a, Point b, Point c) {
	return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
}

bool cmp(const Point &a, const Point &b) {
	ld prod = crossproduct(o, a, b);

	if (prod == 0)
		return dist(o, a) < dist(o, b);

	return prod > 0;
}

Point v[NMAX];
int main() {
	int n;
	fin >> n;

	for (int i = 1; i <= n; i++) {
		fin >> v[i].x >> v[i].y;
	}

	int lowest = 1;
	for (int i = 2; i <= n; i++) {
		if (v[i].y < v[lowest].y ||
			v[i].y == v[lowest].y && v[i].x < v[lowest].x)
			lowest = i;
	}

	swap(v[1], v[lowest]);
	o = v[1];

	sort(v + 2, v + n + 1, cmp);

	vector<Point> hull;
	hull.push_back(v[1]);
	for (int i = 2; i <= n; i++) {
		while (hull.size() >= 2 &&
			   crossproduct(hull[hull.size() - 2], hull.back(), v[i]) <= 0)
			hull.pop_back();

		hull.push_back(v[i]);
	}

	fout << hull.size() << '\n';

	fout << fixed << setprecision(12);
	for (auto it : hull) {
		fout << it.x << ' ' << it.y << '\n';
	}
	return 0;
}