Cod sursa(job #2524042)

Utilizator lflorin29Florin Laiu lflorin29 Data 14 ianuarie 2020 23:24:58
Problema Infasuratoare convexa Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.15 kb
#include <bits/stdc++.h>

using namespace std;

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

const int MAX_N = 120003;

const double EPS = 1e-12;

int n;
pair<double, double>p[MAX_N];
vector<pair<double, double>>hull;
pair<double,double>center;
inline double cross(pair<double, double>a, pair<double, double>b, pair<double, double>c)
{
	return (a.first - c.first) * (b.second - c.second) - (a.second - c.second) * (b.first - c.first);
}

inline bool cmp(const pair<double, double>&a, const pair<double, double>&b)
{
	return cross(center, a, b) < EPS;
}

void gethull()
{
	for (int i = 1; i <= n; ++i)
	{
		while (hull.size() >= 2 && cross(hull[hull.size() - 2], hull[hull.size() - 1], p[i]) > EPS)
			hull.pop_back();

		hull.push_back(p[i]);
	}
}

void Printhull()
{
	fout << hull.size() << '\n';
	fout << fixed << setprecision(12);
	reverse(begin(hull), end(hull));
	for (auto i : hull)
		fout << i.first << ' ' << i.second << '\n';
}
int main()
{
	fin >> n;

	for (int i = 1; i <= n; ++i)
	{
		fin >> p[i].first >> p[i].second;
		center.first+=p[i].first;
		center.second+=p[i].second;

	}

	sort(p + 1, p + n + 1, cmp);
	gethull (), Printhull();
}