Cod sursa(job #1374999)

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


typedef std::vector<int>::iterator iter;
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 (x == v.x) {
			return y > v.y;
		}
		return x > v.x;
	}
	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<int> ind, sol;


inline bool cmp(const int a, const int b)
{
	vec2 p1 = p[a] - p[ref];
	vec2 p2 = p[b] - p[ref];
	
	return p1.x * p2.y < p2.x * p1.y;
}


bool sgn(int a, int b, int c)
{
	return p[a].x * p[b].y + p[b].x * p[c].y + p[c].x * p[a].y - p[a].x * p[c].y - p[b].x * p[a].y - p[c].x * p[b].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 (i != ref) {
			ind.push_back(i);
		}
	}
	sort(ind.begin(), ind.end(), cmp);


	for (int i = 0; i < ind.size(); i++) {
		while (sol.size() > 1 && sgn(*(sol.end() - 2), *(sol.end() - 1), ind[i])) {
			sol.pop_back();
		}
		sol.push_back(ind[i]);
	}
	sol.push_back(ref);
	std::reverse(sol.begin(), sol.end());


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


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