Geometria Computacional: Algoritmos Avançados

Metáfora e Motivação

Quando paramos de fofocar sobre pontos únicos e começamos a resolver problemas populacionais da Geometria Urbana (Exemplo: “Qual o comprimento mínimo de fio para contornar todos os prédios de uma cidade inteira?”). O rei de todos é o infame Convex Hull (Fecho Convexo).

Convex Hull

Imagine um lenhador que espetou dezenas de pregos no painel. Ele laça um elástico enorme nas bordas e solta. O elástico irá encostar com força brutal apenas nos pregos limítrofes extremos, criando um polígono convexo. Todos os outros dezenas de pregos irrelevantes repousam seguros e protegidos dentro da figura sem jamais tocar no elástico externo.

Existem duas abordagens velozes: * Algoritmo de Graham Scan: Ordena pontos por ângulo polar (Radial) focando num pivô basal baixo. Complexidade \(\mathcal{O}(N \log N)\). * Monotone Chain (Cadeia Monótona / Algoritmo de Andrew): Mais moderno e fácil de codar sem perigo com divisões radiais. Você ordena puramente pela abcissa X ordinária e monta a casca (Superior e Inferior) avaliando curvas com o Cross Product bruto!

Solução Monotone Chain (C++)

Garantimos a complexidade sublime \(\mathcal{O}(N \log N)\) graças ou sort primário. O resto consome força bruta linear no recuo de elásticos inválidos.

#include <iostream>
#include <vector>
#include <algorithm>
#include <cassert>

using namespace std;

struct Point {
    long long x, y;
    // Opcional comparador para Sort em Cadeia (Por X, se der empate decida no Y pra quebrar o laço)
    bool operator< (const Point& outro) const {
        if(x == outro.x) return y < outro.y;
        return x < outro.x;
    }
};

// O Monstro do Fecho Convexo
long long crossProduct(Point O, Point A, Point B) {
    return (A.x - O.x) * (B.y - O.y) - (A.y - O.y) * (B.x - O.x);
}

vector<Point> calcularConvexHull(vector<Point>& P) {
    int n = P.size();
    if(n <= 3) return P; 

    // 1. Ordene tudo horizontalmente. O(N log N)
    sort(P.begin(), P.end());

    vector<Point> hull;
    
    // 2. Erguendo a Casa de Baixo
    for(int i = 0; i < n; i++) {
        // Regra do elastico: Equanto os ultimos 3 tentarem formar viradas covardes p/ DENTRO (< 0) -> ROUBO! Corte!
        while(hull.size() >= 2 && crossProduct(hull[hull.size()-2], hull[hull.size()-1], P[i]) <= 0) {
            hull.pop_back();
        }
        hull.push_back(P[i]);
    }
    
    // 3. Descendo o Telhado (Teto) a partir do fim para juntar com a casa
    for(int i = n - 2, t = hull.size() + 1; i >= 0; i--) {
        while(hull.size() >= t && crossProduct(hull[hull.size()-2], hull[hull.size()-1], P[i]) <= 0) {
            hull.pop_back();
        }
        hull.push_back(P[i]);
    }

    hull.pop_back(); // A ultima insercao p/ fechar era copia da base raiz e já tá inserida. Limpa duplicata.
    return hull;
}

void executando_testes() {
    // Mesmos pregos do Desenho (Adicionando a origem, bordas e os inuteis)
    vector<Point> pregos = { {0,0}, {4,0}, {5,5}, {1,6}, {2,2}, {3,3} };
    
    vector<Point> oRetratoDoElastico = calcularConvexHull(pregos);
    
    // Devem sobrar APENAS 4 pilastras externas! 2 inuteis foram esmagados no lixo.
    assert(oRetratoDoElastico.size() == 4);
    
    cout << "[✅] Testes do Polígono de Fita Convexo (Monotone Chain) executados com sucesso!\n";
}

int main() {
    executando_testes();
    return 0;
}

Problema Clássico de Cerco Numérico

Problema: Novos Computadores (Convex Hull) Link: Beecrowd 1982

Solução Aplicada: Encontrar o comprimento mínimo absoluto de fios puros para cercar um grupo irregular de computadores industriais. O calcularConvexHull joga todo o lixo do meio fora sobrando \(K\) pontos externos, e você simplesmente escreve um loop final com o hypot Euclidiano somando o segmento dos índices \(0\rightarrow1, 1\rightarrow2 ...\text{ e } K \rightarrow 0\).

Prática Avançada (Algoritmos Espaciais)

[Par de Pontos Mais Próximos]
- Foco: Problema brutal de Divisão e Conquista. Dado um bilhão de meteoros no mapa \(\mathcal{O}(N^2)\) explode a máquina! Para achar os 2 meteoros mais próximos sem cruzar todos com todos, usa-se sub-grid Divide & Conquer cravado em \(O(N \log N)\).
- Link: Beecrowd 1295 (Ótimo treino de fronteiras).
[Fábrica de Chocolate]
- Foco: Triangulações e testes de inclusão / áreas parciais.
- Link: Beecrowd 1296 (Medianas de Triângulo baseadas na fórmula do triângulo original com escala restrita 4/3).