convex_hull.cpp

// Convex Hull O(n*log(n))
// por Lawrence Melo

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

struct point
{
	int x, y;

	bool operator <(const point &p) const 
	{
		return x < p.x || (x == p.x && y < p.y); // ordenar por x e uso y para desempate
	}
};

vector<point> pt; // pontos do plano

ll cross(point o, point a, point b)
{
	return (a.x - o.x)*(ll)(b.y - o.y) - (a.y - o.y)*(ll)(b.x - o.x); 
	// retorno o sentido do giro (horario ou anti-horario)
	// Note que se nao houver giro, a funcao retorna 0, ou seja os pontos estao alinhados
	// cabe apenas ao contexto da questao considerar pontos alinhados como parte da envoltoria
}

vector<point> CH()
{
	int sz = pt.size(), k = 0; //k eh o numero de pontos na envoltoria
	
	vector<point> H(2*sz);

	sort(pt.begin(), pt.end());

	for(int i = 0; i < sz; i++) //parte superior 
	{
		while(k >= 2 && cross(H[k - 2], H[k - 1], pt[i]) <= 0) k--; //se gira para a esquerda, removo o penultimo
		H[k++] = pt[i]; //adiciono o ponto
	}

	for(int i = sz - 2, t = k + 1; i >= 0; i--) //parte inferior
	{
		while(k >= t && cross(H[k - 2], H[k - 1], pt[i]) <= 0) k--; //se gira para a direita, removo o penultimo
		H[k++] = pt[i]; // parte inferior
	}
	
	H.resize(k);
	return H;
}