Cod sursa(job #3349072)

Utilizator Ruxandra009Ruxandra Vasilescu Ruxandra009 Data 25 martie 2026 12:06:36
Problema Infasuratoare convexa Scor 10
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.06 kb
#include <algorithm>
#include <iomanip>
#include <fstream>
#include <vector>

using namespace std;

ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");

struct point {
	double x, y;
};

const int nmax = 120005;
point v[nmax];

int det(point a, point b, point c)
{
	int d1 = (b.x - a.x) * (c.y - a.y);
	int d2 = (c.x - a.x) * (b.y - a.y);

	if (d1 == d2) return 0;
	return (d1 > d2 ? 1 : -1);
}

bool cmp(point a, point b) {
	return a.y < b.y;
}

int main()
{
	int n; f >> n;
	for (int i = 1; i <= n; i++)
		f >> v[i].x >> v[i].y;
	
	sort(v + 1, v + n + 1, cmp);
	
	vector<point> ans; ans.clear();
	for (int i = 1; i <= n; i++)
	{
		while (ans.size() > 1 && det(ans[ans.size() - 2], ans.back(), v[i]) < 0) ans.pop_back();
		ans.push_back(v[i]);
	}

	for (int i = n - 1; i > 1; i--)
	{
		while (ans.size() > 1 && det(ans[ans.size() - 2], ans.back(), v[i]) < 0) ans.pop_back();
		ans.push_back(v[i]);
	}

	g << ans.size() << '\n';
	for (auto a : ans) g << setprecision(12) << fixed << a.x << " " << a.y << '\n';
	return 0;
}