Geometria Computacional: Algoritmos

Introdução Teórica

Algoritmos que resolvem problemas geométricos de “grande escala”, envolvendo coleções de pontos ou formas.

Convex Hull (Fecho Convexo)

Imagine um quadro com vários pregos (pontos). Se soltarmos um elástico ao redor de todos, ele se contrairá formando um polígono que envolve todos os pontos. Esse é o Convex Hull. * Algoritmo de Graham Scan: Ordena pontos por ângulo polar. * Monotone Chain: Ordena por coordenada X. Constrói a borda superior e inferior separadamente usando Cross Product para manter a convexidade (“sempre vire à direita”). Complexidade \(O(N \log N)\).

Problema Clássico

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

Descrição: Encontrar o comprimento mínimo de fita para cercar um grupo de computadores. Isso é exatamente o perímetro do Convex Hull.

Solução: 1. Implementar Monotone Chain. 2. Calcular a distância Euclideana entre pontos adjacentes no Hull. 3. Somar.

Variações e Exercícios

  1. [Par de Pontos Mais Próximos]
    • Foco: Problema clássico de Divisão e Conquista. Força bruta é \(O(N^2)\), inaceitável para \(N=10000\). O algoritmo otimizado é \(O(N \log N)\).
    • Link: Beecrowd 1295 (Extremamente chato com casos de borda, ótimo treino de precisão).
  2. [Fábrica de Chocolate]
    • Foco: Polígonos e testes de inclusão.
    • Link: [Beecrowd 1296] (Medianas - Triângulo). Procure problemas sobre área de polígonos.
  3. [Linhas de Metrô]
    • Foco: Intersecção de linhas e segmentos.
Back to top