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.

🔗 Relacionados