Please enable JavaScript.
Coggle requires JavaScript to display documents.
Capítulo 7: (Computational) Geometry - Coggle Diagram
Capítulo 7: (Computational) Geometry
7.1 Overview and Motivation
Geometria cai pouco → risco de WA alto
Muitos casos especiais: colinearidade, vértices repetidos, concavidade
Imprecisão numérica (ponto flutuante)
Implementações longas
Tipos:
Pure geometry → resolução manual
Computational geometry → requer algoritmos + código
Importância:
Quase todo ICPC tem 1+ problemas de geometria
Rotinas prontas aumentam chance de AC
7.2 Basic Geometry Objects with Libraries
7.2.1 Points (0D)
Representação: (x, y)
Comparação:
Menor: por x, depois y
Igualdade: |dx| < EPS e |dy| < EPS
Operações:
Distância: hypot(dx,dy)
Rotação por θ:
x' = x cosθ − y sinθ
y' = x sinθ + y cosθ
7.2.2 Lines (1D)
Equação geral: ax + by + c = 0
Construção: pointsToLine(p1,p2)
Testes:
Paralelas: |a1−a2| < EPS e |b1−b2| < EPS
Iguais: paralelas e |c1−c2| < EPS
Interseção:
Resolver sistema linear
Distância ponto-linha:
usar projeção vetorial
Segmento:
testar extremos e projeção
CCW Test:
cross(a→b, a→c)
0 esquerda
<0 direita
=0 colinear
7.2.3 Circles (2D)
Testes:
ponto dentro → dist² < r²
ponto na borda → dist² ≈ r²
ponto fora → dist² > r²
Propriedades:
Diâmetro = 2r
Perímetro = 2πr
Área = πr²
Arco, setor e segmento:
Setor = θ/360 • πr²
Segmento = setor − triângulo
7.2.4 Triangles
Tipos: equilátero, isósceles, escaleno, retângulo
Perímetro: a+b+c
Semi-perímetro: s = (a+b+c)/2
Área:
Heron: sqrt(s(s−a)(s−b)(s−c))
Incircle:
raio = A/s
centro = bissetrizes
Circumcircle:
raio = abc / (4A)
centro = mediatrizes
Trigonometria:
Lei dos Cossenos
Lei dos Senos
Teorema de Pitágoras
Triplas Pitagóricas
7.2.5 Quadrilaterals
Quadrilateral = polígono com 4 lados
Tipos:
Retângulo
Quadrado
Trapézio e Isósceles Trapézio
Paralelogramo
Kite
Losango
7.3 Algorithms on Polygon with Libraries
7.3.1 Representação de Polígonos
Lista de pontos em ordem cw ou ccw
Repetir P[0] no fim
7.3.2 Perimeter
Soma das distâncias consecutivas
7.3.3 Area
Fórmula do Shoelace (determinante)
Sinal indica orientação: ccw positivo
7.3.4 Checking if Polygon is Convex
Verificar sinais de todas as CCW
Se sinais variam → polígono concavo
7.3.5 Point Inside Polygon
Winding number:
Somar ângulos com sinal
≈2π → dentro
≈0 → fora
Casos especiais:
Ponto na borda
7.3.6 Cutting Polygon with Line
Iterar vértices
Adicionar:
vértices no lado esquerdo
interseção quando cruzar linha
Usado para:
meio-plano
clipping
7.3.7 Convex Hull
Analogia: banda elástica envolvendo pregos
Graham Scan (O(n log n)):
Escolher pivot (menor y)
Ordenar por ângulo
Stack:
pop enquanto right turn
Andrew Monotone Chain:
Ordenar por x
Construir lower hull
Construir upper hull
Mais rápido (evita atan2)