Cod sursa(job #3237878)

Utilizator Cezar2009Cezar Mihai Titihazan Cezar2009 Data 13 iulie 2024 22:06:59
Problema Infasuratoare convexa Scor 20
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.47 kb
//https://infoarena.ro/problema/infasuratoare
//#pragma GCC optimize ("Ofast")
//#pragma GCC optimize ("fast-math")
//#pragma GCC optimize ("unroll-loops")
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;

#define PDD pair<double,double>

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

PDD v0;

double arie(const PDD& a, const PDD& b, const PDD& c)
{
	double x = a.first * b.second - a.second * b.first;
	double y = b.first * c.second - b.second * c.first;
	double z = c.first * a.second - c.second * a.first;
	return x + y + z;
}
bool comparare(const PDD& a, const PDD& b)
{
	return arie(v0, a, b) > 0;
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int n, i;
	double x, y;
	vector <PDD> v;
	vector <int> st;

	fin >> n;
	for (i = 0; i < n; ++i)
	{
		fin >> x >> y;
		v.emplace_back(x, y);
		if (v[i].first < v[0].first)
		{
			PDD cc = v[i];
			v[i] = v[0];
			v[0] = cc;
		}
	}
	v0 = v[0];
	sort(v.begin() + 1, v.end(), comparare);

	/*for (i = 0; i < n; ++i)
	{
		cout << v[i].first << " " << v[i].second << "\n";
	}*/

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

	fout << st.size() << "\n";
	for (auto& x : st)
	{
		fout << v[x].first << " " << v[x].second << "\n";
	}

	return 0;
}