Convex hull
Tema: Geometría · temarios: Syllabus OCI · Syllabus IOI
📍 Para profundizar: esta ficha amplía las clases de la Ruta de Aprendizaje. Puedes estudiarla cuando un problema requiera esta herramienta.
Qué hace
La envolvente convexa de un conjunto de puntos (el polígono convexo mínimo que los contiene), por el método de Andrew (monotone chain).
Complejidad: O(n log n) por el ordenamiento.
Cuándo usarlo
Envolvente convexa, diámetro de un conjunto de puntos, problemas de ‘el polígono más externo’.
Implementación recomendada (C++)
struct P { long long x, y; bool operator<(const P& o) const { return x < o.x || (x == o.x && y < o.y); } };
long long cross(const P& O, const P& A, const P& B) {
return (A.x - O.x) * (B.y - O.y) - (A.y - O.y) * (B.x - O.x);
}
vector<P> convex_hull(vector<P> p) { // p por valor a propósito: se ordena una copia
int n = p.size(), k = 0;
if (n < 3) return p;
sort(p.begin(), p.end());
vector<P> h(2 * n);
for (int i = 0; i < n; i++) { // borde inferior
while (k >= 2 && cross(h[k-2], h[k-1], p[i]) <= 0) k--;
h[k++] = p[i];
}
for (int i = n - 2, t = k + 1; i >= 0; i--) { // borde superior
while (k >= t && cross(h[k-2], h[k-1], p[i]) <= 0) k--;
h[k++] = p[i];
}
h.resize(k - 1);
return h;
}⚠️ Notas
<= 0 descarta puntos colineales del borde; usa < 0 si los quieres conservar. Devuelve los vértices en sentido antihorario. Elimina los puntos repetidos antes (sort + unique). Ojo con el nombre: el convex hull trick (Convex hull trick (Li Chao)) es otra cosa — una optimización de DP que no construye ningún polígono.