Cod sursa(job #1374757)

Utilizator MarronMarron Marron Data 5 martie 2015 10:40:30
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.56 kb
#include <algorithm>
#include <iostream>
#include <fstream>
#include <vector>
#include <iomanip>


#define x first
#define y second


const int MAXN = 120005;
std::ifstream f("infasuratoare.in");
std::ofstream g("infasuratoare.out");
std::pair<double, double> p[MAXN]; int n, ref = 1;
std::vector<int> ind, sol;


inline bool cmp(int a, int b)
{
	std::pair<double, double> p1 = std::make_pair(p[a].x - p[ref].x, p[a].y - p[ref].y);
	std::pair<double, double> p2 = std::make_pair(p[b].x - p[ref].x, p[b].y - p[ref].y);

	return p1.x * p2.y < p2.x * p1.y;
}


bool sgn(int a, int b, int c)
{
	std::pair<double, double> p1 = p[a];
	std::pair<double, double> p2 = p[b];
	std::pair<double, double> p3 = p[c];

	return p1.x * p2.y + p2.x * p3.y + p3.x * p1.y - p1.x * p3.y - p2.x * p1.y - p3.x * p2.y >= 0;
}


int main()
{
	f >> n;
	for (int i = 1; i <= n; i++) {
		f >> p[i].x >> p[i].y;
		
		if (p[ref] > p[i]) {
			ref = i;
		}
	}

	for (int i = 1; i <= n; i++) {
		if (p[i] != p[ref]) {
			ind.push_back(i);
		}
	}


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


	for (int i = 1; i <= n; i++) {
		while (sol.size() > 1 && sgn(*(sol.end() - 2), *(sol.end() - 1), i)) {
			sol.pop_back();
		}
		sol.push_back(i);
	}


	g << sol.size() + 1 << std::endl;
	for (int i = 0; i < sol.size(); i++) {
		g << std::fixed << std::setprecision(6) << p[sol[i]].x << ' ' << p[sol[i]].y << '\n';
	}
	g << std::fixed << std::setprecision(6) << p[ref].x << ' ' << p[ref].y << std::endl;



	//system("pause");
	f.close();
	g.close();
	return 0;
}