Cod sursa(job #2039853)

Utilizator robuvedVictor Robu robuved Data 15 octombrie 2017 00:04:57
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 2.03 kb
#include <fstream>
#include <vector>
#include <iomanip>
#include <stack>
#include <algorithm>
using namespace std;
ifstream in("infasuratoare.in");
ofstream out("infasuratoare.out");
struct Point
{
	double x, y;
};
enum Dir{CW, CCW, CL};
#define MAX 120000
Point v[MAX];
int hull[MAX];
int N, k;

double Dist(Point a, Point b)
{
	double dx = a.x - b.x;
	double dy = a.y - b.y;
	return dx * dx + dy * dy;
}
Dir Direction(Point& a, Point& b, Point& c)
{
	Point ab{ b.x - a.x, b.y - a.y };
	Point ac{ c.x - a.x, c.y - a.y };
	double crossp = ab.x * ac.y - ab.y * ac.x;
	return (crossp < 0) ? CW : (crossp > 0 ? CCW : CL);
}
Point current_point;
bool Compare(Point& a, Point& b)
{
	return Direction(current_point, a, b) == CCW;
}
void Jarvis()
{
	int min_x = 0;
	for (int i = 1; i < N; i++)
	{
		if (v[i].x < v[min_x].x)
			min_x = i;
	}
	k = 0;
	int current = min_x;
	int next;
	do{
		hull[k++] = current;
		next = 0;
		for (int i = 1; i < N; i++)
		{
			Dir o = Direction(v[current], v[next], v[i]);
			if (current == next || o == CW ||
				(o == CL && Dist(v[current], v[next]) < Dist(v[current], v[i])))
			{
				next = i;
			}
		}
		current = next;
	} while (current != hull[0]);
}
void Graham()
{
	int min_x = 0;
	for (int i = 1; i < N; i++)
	{
		if (v[i].x < v[min_x].x)
			min_x = i;
	}
	current_point = v[min_x];
	swap(v[0], v[min_x]);
	sort(v + 1, v + N, Compare);

	hull[k++] = 0;
	hull[k++] = 1;
	for (int i = 2; i < N; i++)
	{
		int top = hull[k - 1];
		int prev = hull[k - 2];
		Dir o = Direction(v[prev], v[top], v[i]);
		while (o == CW || (o == CL && Dist(v[prev], v[top]) < Dist(v[prev], v[i])))
		{
			k--;
			int top = hull[k - 1];
			int prev = hull[k - 2];
			o = Direction(v[prev], v[top], v[i]);
		}
		hull[k++] = i;
	}
}
int main()
{
	in >> N;
	for (int i = 0; i < N; i++)
	{
		in >> v[i].x >> v[i].y;
	}
	Graham();
	out << k << '\n';
	for (int i = 0; i < k; i++)
	{
		out << fixed << setprecision(8) << v[hull[i]].x << ' ' << v[hull[i]].y << '\n';
	}
}