Cod sursa(job #2721308)

Utilizator FrostfireMagirescu Tudor Frostfire Data 11 martie 2021 18:23:04
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.35 kb
#include <iostream>
#include <fstream>
#include <iomanip>
#include <algorithm>
#define NMAX 120000
#define ld long double
#define f first
#define s second
#define inf 2000000000

using namespace std;

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

int n, m;
pair <ld, ld> v[NMAX+10];
pair <ld, ld> LL = {inf, inf}, stiva[NMAX+10];

bool mycmp(pair <ld, ld> a, pair <ld, ld> b)
{	return a.s * b.f < a.f * b.s;
}

int A(pair <ld, ld> a, pair <ld, ld> b, pair <ld, ld> c)
{	ld val = (a.f - b.f) * (a.s - c.s) - (a.s - b.s) * (a.f - c.f);
	if(val < 0) return -1;
	return 1;
}

int main()
{
	fin >> n;
	for(int i=1; i<=n; i++)
		{	fin >> v[i].f >> v[i].s;
			if(v[i].s < LL.s)
				LL = v[i];
			else if(v[i].s == LL.s && v[i].f < LL.f)
				LL = v[i];
		}
	for(int i=1; i<=n; i++)
		{	if(v[i] == LL)
				continue;
			v[++m] = {v[i].f - LL.f, v[i].s - LL.s};
		}
	n = m;
	v[0] = {0, 0};
	sort(v+1, v+n+1, mycmp);
	stiva[1] = {0, 0};
	stiva[2] = v[1];
	stiva[3] = v[2];
	int vf = 3;
	for(int i=3; i<=n; i++)
		{	while(vf >= 3 && A(stiva[vf-2], stiva[vf-1], stiva[vf]) != A(stiva[vf-1], stiva[vf], v[i]))
				vf--;
			stiva[++vf] = v[i];
		}
	fout << vf << '\n';
	fout << setprecision(12) << fixed;
	for(int i=1; i<=vf; i++)
		fout << stiva[i].f + LL.f << ' ' << stiva[i].s + LL.s << '\n';
	return 0;
}