Cod sursa(job #3279356)

Utilizator alex_0747Gheorghica Alexandru alex_0747 Data 22 februarie 2025 17:43:25
Problema Infasuratoare convexa Scor 60
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.12 kb
#include <bits/stdc++.h>
using namespace std;

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

struct Punct
{
	double x, y;
	bool operator< (Punct A) const
	{
		if (y == A.y)
			return x < A.x;
		return y < A.y;
	}
};

Punct a[120005];
int n, st[120005], v[120005];

double Plan(Punct A, Punct B, Punct C)
{
	double a = (A.y - B.y);
	double b = (B.x - A.x);
	double c = A.x * B.y - A.y * B.x;
	return a * C.x + b * C.y + c;
}

int main()
{
	int i, top;
	fin >> n;
	for (i = 1; i <= n; i++)
		fin >> a[i].x >> a[i].y;

	sort(a + 1, a + n + 1);
	top = 0;
	st[++top] = 1; st[++top] = 2;
	v[1] = v[2] = 1;
	for (i = 3; i <= n; i++)
	{
		while (top > 1 && Plan(a[st[top - 1]], a[st[top]], a[i]) <= 0)
		{
			v[st[top]] = 0;
			top--;
		}
		st[++top] = i;
		v[i] = 1;
	}

	for (i = n - 1; i >= 1; i--)
	{
		if (v[i]) continue;
		while (top > 1 && Plan(a[st[top - 1]], a[st[top]], a[i]) <= 0)
			top--;
		st[++top] = i;
	}

	fout << top << "\n";
	for (i = 1; i <= top; i++)
		fout << fixed << setprecision(6) << a[st[i]].x << " " << a[st[i]].y << "\n";
	return 0;
}