Cod sursa(job #2039796)

Utilizator robuvedVictor Robu robuved Data 14 octombrie 2017 22:49:17
Problema Infasuratoare convexa Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 1.53 kb
#include <fstream>
#include <vector>
using namespace std;
ifstream in("infasuratoare.in");
ofstream out("infasuratoare.out");
typedef pair<double, double> Point;
enum Dir{CW, CCW, CL};
double Dist(Point a, Point b)
{
	double dx = a.first - b.first;
	double dy = a.second - b.second;
	return dx * dx + dy * dy;
}
Dir Direction(Point a, Point b, Point c)
{
	Point ab({ b.first - a.first, b.second - a.second });
	Point ac({ c.first - a.first, c.second - a.second });
	double crossp = ab.first * ac.second - ab.second * ac.first;
	if (crossp < 0)
		return CW;
	else if (crossp > 0)
		return CCW;
	else
		return CL;
}
vector<int> Jarvis(vector<pair<double, double>> &v)
{
	int min_x = 0;
	for (int i = 1; i < v.size(); i++)
	{
		if (v[i].first < v[min_x].first)
			min_x = i;
	}
	vector<int> hull;
	int current = min_x;
	int next = (current + 1) % v.size();
	while (hull.empty() || current != hull.front())
	{
		hull.push_back(current);
		for (int i = 0; i < v.size(); i++)
		{
			Dir o = Direction(v[current], v[next], v[i]);
			if (o == CW || (o == CL && Dist(v[current], v[next]) < Dist(v[current], v[i])))
			{
				next = i;
			}
		}
		current = next;
		next = hull.front();
	}
	return hull;
}
int main()
{
	int N;
	in >> N;
	vector<pair<double, double>> v(N);
	for (int i = 0; i < N; i++)
	{
		in >> v[i].first >> v[i].second;
	}
	vector<int> hull = Jarvis(v);
	out << hull.size() << '\n';
	for (int i = 0; i < hull.size(); i++)
	{
		out << v[hull[i]].first << ' ' << v[hull[i]].second << '\n';
	}
}