Cod sursa(job #1374855)

Utilizator MarronMarron Marron Data 5 martie 2015 11:04:38
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.51 kb
#include <algorithm>
#include <iostream>
#include <fstream>
#include <vector>
#include <iomanip>

using namespace std;
typedef vector<int>::iterator iter;

#define MAXN 120005

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

int n, pi = 1;
pair<double, double> pt[MAXN];
vector<int> ind, sol;

inline bool cmp(int a, int b) {
	return (double)(pt[a].first - pt[pi].first) * (pt[b].second - pt[pi].second) < (double)(pt[b].first - pt[pi].first) * (pt[a].second - pt[pi].second);
}

bool sgn(int a, int b, int c) {
	return ((long double)pt[a].first * pt[b].second + pt[b].first * pt[c].second + pt[c].first * pt[a].second - pt[a].second * pt[b].first - pt[b].second * pt[c].first - pt[c].second * pt[a].first) > 0;
}

int main()
{
	f >> n;
	for (int i = 1; i <= n; i++) {
		f >> pt[i].first >> pt[i].second;

		if (pt[pi].first > pt[i].first || (pt[pi].first == pt[i].first && pt[pi].second > pt[i].second)) {
			pi = i;
		}
	}
	for (int i = 1; i <= n; i++) {
		if (i != pi) {
			ind.push_back(i);
		}
	}

	sort(ind.begin(), ind.end(), cmp);

	for (iter it = ind.begin(); it != ind.end(); it++) {
		while (sol.size() > 1 && sgn(*(sol.end() - 2), *(sol.end() - 1), *it)) {
			sol.pop_back();
		}
		sol.push_back(*it);
	}
	sol.push_back(pi);

	reverse(sol.begin(), sol.end());

	g << sol.size() << '\n';
	for (iter it = sol.begin(); it != sol.end(); it++) {
		g << setprecision(32) << pt[*it].first << ' ' << pt[*it].second << '\n';
	}

	f.close();
	g.close();
	return 0;
}