Cod sursa(job #2201479)

Utilizator emiemiEmi Necula emiemi Data 4 mai 2018 21:34:20
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.03 kb
#include <fstream>
#include <iomanip>
#include <algorithm>

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

#define NMAX 120005
#define pd pair<double, double>

pd v[NMAX];
pd st[NMAX];

double sinABC(pd A, pd B, pd C) {
	return ((C.second - B.second) * (A.first - B.first) -
		(C.first - B.first) * (A.second - B.second));
}

bool cmp(pd a, pd b) {
	return (sinABC(v[1], a, b) < 0);
}

int main() {
	int i, n;

	f >> n;
	for (i = 1; i <= n; ++i)
		f >> v[i].first >> v[i].second;

	int pos;
	pd maxi = v[1];
	for (i = 2; i <= n; ++i)
		if (v[i] < maxi) {
			maxi = v[i];
			pos = i;
		}
	swap(v[1], v[pos]);

	sort(v + 1, v + n + 1, cmp);
	
	int len = 2;
	st[1] = v[1];
	st[2] = v[2];

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

	g << len << '\n';
	for (i = 1; i <= len; ++i) {
		g << fixed << setprecision(12) << st[i].first << ' ' << st[i].second << '\n';
	}

	return 0;
}