Tópicos Avançados de Algoritmos

1. Geometria Computacional: O Poder do Produto Vetorial

Em Geometria Computacional, evitamos ao máximo usar ângulos, trigonometria (sin, cos, atan2) ou divisão, pois a imprecisão do double acumula. A ferramenta suprema é o Produto Vetorial (Cross Product).

Dados dois vetores \(\vec{A}\) e \(\vec{B}\), o Cross Product em 2D é \(A_x B_y - A_y B_x\). - Positivo: \(\vec{B}\) está à esquerda de \(\vec{A}\) (Sentido Anti-horário). - Negativo: \(\vec{B}\) está à direita de \(\vec{A}\) (Sentido Horário). - Zero: Colineares.

Aplicações

  1. Área de Polígono: A área é \(\frac{1}{2} | \sum (x_i y_{i+1} - x_{i+1} y_i) |\).
  2. Interseção de Segmentos: Se os extremos de um segmento estão em lados opostos da reta do outro segmento (testado com Cross Product), e vice-versa, eles cruzam.
  3. Convex Hull (Fecho Convexo): Encontrar o menor polígono convexo que engloba um conjunto de pontos (como um elástico). Algoritmo Monotone Chain (\(O(N \log N)\)).

2. Strings e Dicionários

Trie (Árvore de Prefixos)

Estrutura para armazenar um dicionário de palavras. Cada aresta é uma letra. Muito usado em Autocomplete e Corretores Ortográficos.

class TrieNode {
    TrieNode[] children = new TrieNode[26];
    boolean isEndOfWord;
}

public void insert(String word) {
    TrieNode curr = root;
    for (char c : word.toCharArray()) {
        int idx = c - 'a';
        if (curr.children[idx] == null) {
            curr.children[idx] = new TrieNode();
        }
        curr = curr.children[idx];
    }
    curr.isEndOfWord = true;
}

KMP (Knuth-Morris-Pratt)

Imagine buscar a palavra “ANA” dentro de “BANANA”. O algoritmo ingênuo é \(O(N \cdot M)\). O KMP pré-processa o padrão para saber “quanto posso pular” se falhar. Cria o array LPS (Longest Prefix Suffix). Complexidade: \(O(N + M)\).

3. LCA (Lowest Common Ancestor)

Dado uma árvore, quem é o ancestral comum mais próximo entre \(u\) e \(v\)? Exemplo: Em Biologia (Árvore Filogenética), o LCA de Humano e Chimpanzé é um primata ancestral comum.

Solução Lenta: Subir os pais de um até a raiz, marcar o caminho, subir o outro até achar um marcado. \(O(N)\) por consulta. Lento.

Solução Rápida (Binary Lifting): Pré-processamos uma tabela up[u][i] que guarda o \(2^i\)-ésimo ancestral de \(u\). Isso permite “saltar” potências de 2 na árvore (\(1, 2, 4, 8 \dots\)). - Pré-processamento: \(O(N \log N)\). - Consulta LCA: \(O(\log N)\).

// up[u][i] = 2^i-th ancestor of u
void preprocess(int root) {
    // DFS para calcular up[u][0] (pai direto) e profundidade...
    
    // DP para calcular as potências
    for (int i = 1; i <= MAX_LOG; i++) {
        for (int u = 0; u < N; u++) {
            if (up[u][i-1] != -1) {
                up[u][i] = up[up[u][i-1]][i-1];
            } else {
                up[u][i] = -1;
            }
        }
    }
}

int lca(int u, int v) {
    if (depth[u] < depth[v]) return lca(v, u); // u deve ser mais fundo
    
    // 1. Sobe u para o mesmo nível de v
    for (int i = MAX_LOG; i >= 0; i--) {
        if (depth[u] - (1 << i) >= depth[v]) {
            u = up[u][i];
        }
    }
    
    if (u == v) return u;
    
    // 2. Sobem juntos até logo abaixo do LCA
    for (int i = MAX_LOG; i >= 0; i--) {
        if (up[u][i] != up[v][i]) {
            u = up[u][i];
            v = up[v][i];
        }
    }
    
    return up[u][0]; // Pai do ponto de parada é o LCA
}

Isso é vital para calcular distância entre nós em árvore: \(Dist(u, v) = Depth(u) + Depth(v) - 2 \cdot Depth(LCA(u, v))\).

Back to top