Cod sursa(job #1374469)

Utilizator MarronMarron Marron Data 5 martie 2015 09:29:34
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.51 kb
#include <algorithm>
#include <iostream>
#include <fstream>
#include <vector>
#include <iomanip>


struct vec2
{
	double x, y;

	vec2(double _x = 0.0, double _y = 0.0) {
		x = _x;
		y = _y;
	}
	bool operator<(const vec2 v) const {
		if (y == v.y) {
			return x < v.x;
		}
		return y < v.y;
	}
	vec2 operator-(const vec2 v) const {
		return vec2(x - v.x, y - v.y);
	}
	bool operator==(const vec2 v) const {
		return (x == v.x && y == v.y);
	}
};


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


inline bool cmp(const vec2 a, const vec2 b)
{
	if (a == p[ref]) {
		return true;
	}
	if (b == p[ref]) {
		return false;
	}
	vec2 p1 = a - p[ref];
	vec2 p2 = b - p[ref];

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


bool sgn(vec2 a, vec2 b, vec2 c)
{
	return a.x * b.y + b.x * c.y + c.x * a.y - a.x * c.y - b.x * a.y - c.x * b.y >= 0;
}


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

		if (p[i] < p[ref]) {
			ref = i;
		}
	}


	std::sort(p + 1, p + n + 1, cmp);
	for (int i = 1; i <= n; i++) {
		while (sol.size() > 1 && sgn(*(sol.end() - 1), *(sol.end() - 2), p[i])) {
			sol.pop_back();
		}
		sol.push_back(p[i]);
	}
	g << sol.size() << '\n';
	for (int i = 0; i < sol.size(); i++) {
		g << std::fixed << std::setprecision(6) << sol[i].x << ' ' << sol[i].y << '\n';
	}

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