Please enable JavaScript.
Coggle requires JavaScript to display documents.
MM12, Geometria - Coggle Diagram
MM12
Geometria
1D — Retas, segmentos e vetores
reta (forma ax + by + c = 0)
convenção: b = 1 para não-verticais; b = 0 para verticais (implementação conveniente)
construir reta por dois pontos p1,p2
interseção de duas retas (a1,b1,c1) e (a2,b2,c2): resolver sistema linear
teste de paralelismo: a1==a2 e b1==b2 (com EPS)
vetor entre p→q: v = (q.x - p.x, q.y - p.y)
produto escalar (dot): u·v = uxvx + uyvy
ângulo entre u e v: θ = acos( (u·v) / (|u||v|) )
produto vetorial (cross) em 2D (valor escalar z):
cross(u,v) = uxvy - uyvx
interpretação: >0 → esquerda (ccw), 0 → collinear, <0 → direita (cw)
distância ponto → reta (infinita) definida por a,b: |cross(b-a, p-a)| / |b-a|
distância ponto → segmento: considerar projeção; se projeção fora dos extremos, distância ao ponto mais próximo
segmento-segmento: checar interseção via orientações + limites (incluindo colinear + overlap)
orientações e robustez: usar cross com EPS, tratar casos colineares separadamente
Funções utilitárias comuns (pseudo/assinaturas)
toVector(a,b) → (b.x-a.x, b.y-a.y)
dot(u,v), cross(u,v)
dist(a,b) → hypot(dx,dy)
distToLine(p, a, b) → |cross(b-a, p-a)| / |b-a|
distToSegment(p, a, b) → min(dist(p,a), dist(p,b), projeção se dentro)
lineFromPoints(a,b) → (a,b,c) (cuidado com vertical)
lineIntersection(l1,l2) → ponto (se não paralelas)
segmentIntersection(a,b,c,d) → checar interseção incluindo colinear
angle(a,o,b) → acos( dot(oa,ob) / (|oa||ob|) )
2D — Triângulos
tipos: equilátero, isósceles, escaleno, retângulo
área base/altura: A = 0.5 * b * h
perímetro p = a + b + c; semiperímetro s = p/2
Heron: A = sqrt(s (s-a)(s-b)(s-c))
raio do incircle: r = A / s
incentro: interseção das bissetrizes angulares (encontrar interseção de duas bissetrizes)
lei dos cossenos: c^2 = a^2 + b^2 - 2ab cos(C)
lei dos senos: a/sin A = b/sin B = c/sin C
2D — Círculos
equação: (x - a)^2 + (y - b)^2 = r^2
posição de ponto: d = distância(p, centro)
d < r → dentro; d = r → na borda; d > r → fora (usar EPS)
perímetro: 2πr; área: πr^2; diâmetro: 2r
arco com ângulo α (graus): comprimento = (α/360) * 2πr
corda com ângulo α (rad): comprimento = 2 r sin(α/2)
alternativa: sqrt(2 r^2 (1 - cos α))
área de setor: (α/360) * π r^2
área de segmento: área setor − área triângulo isósceles (usar trig)
Exercícios resolvidos
Exercise 7.2.1.1: 5.0
Exercise 7.2.1.2: (-3.0, 10.0)
Exercise 7.2.1.3: (-0.674, 10.419)
Exercise 7.2.2.1: Observação — a forma y = m x + c não representa linhas verticais; prefira ax + by + c = 0 para evitar tratamento especial
Exercise 7.2.2.2: -0.5
x + 1.0
y - 1.0 = 0.0
Exercise 7.2.2.3: 1.0
x + 0.0
y - 2.0 = 0.0 (linha vertical x=2)
Exercise 7.2.2.4: Slope m = (y2 - y1) / (x2 - x1); então c = y1 - m*x1 — mas atenção: tratar vertical separadamente se usar y=mx+c
Polígonos — representação e operações
representação: lista de vértices em CCW (ou CW); às vezes repetir o primeiro no fim
perímetro: soma das distâncias entre vértices consecutivos
área (shoelace / determinant):
A = 0.5 * | sum_{i=0..n-1} (xiyi+1 - xi+1yi) |
signed area → positivo se ordenado CCW
checar convexidade:
percorrer tripletas consecutivas e verificar sinal do cross consistente (todos ≥0 ou ≤0)
se qualquer mudança de sinal (excluindo zeros colineares) → concavo
ponto dentro do polígono:
winding number (soma de ângulos) ou ray casting (paridade de interseções)
tratar casos quando ponto está sobre aresta (usar distância/colinearidade)
cortar polígono por reta:
itere vértices; mantenha aqueles do lado desejado; quando aresta cruza reta, adicione ponto de interseção; reconstruir polígono convexo resultante
cuidado com colinearidade e pontos exatamente na reta
Casos de teste importantíssimos
colinearidade total (todos pontos em uma linha)
polígonos concavos com vértices degenerados
ponto exatamente na aresta / vértice do polígono
retas paralelas / coincidentes
segmentos que se tocam apenas nas extremidades
coordenadas negativas e muito grandes (overflow)
Notação e constantes
ponto: (x, y)
vetor v = (vx, vy)
|v| = sqrt(vx^2 + vy^2)
pi = acos(-1.0)
EPS ≈ 1e-9; comparações: a == b → |a-b| < EPS; a ≥ 0 → a > -EPS
2D — Quadriláteros importantes
retângulo: área = w*h, perímetro = 2(w+h)
quadrado: w = h
trapézio: A = 0.5*(w1 + w2)*h
parallelogramo: área = base*altura (ou |cross(AB, AD)|)
kite/rhombus: área = (d1 * d2) / 2
Convex Hull (envelope convexo)
objetivo: menor polígono convexo que contém todos os pontos
Graham Scan (O(n log n)):
escolher pivot: ponto com menor y (em empate, menor x)
ordenar todos os pontos por ângulo polar em relação ao pivot (ou usar monotonic chain / Andrew O(n log n))
percorrer pontos adicionando ao stack; enquanto últimos dois + novo fazem volta não desejada (<=0 ou <0 dependendo de inclusão de pontos colineares), pop
Andrew Monotone Chain (recomendado por simplicidade):
ordenar por x então y; construir lower e upper hull; concatenar sem repetir extremidades
complexidade: O(n log n) por ordenação + O(n) para varredura
cuidado: pontos colineares (incluir/excluir pontos do bordo conforme necessidade)
Implementação prática & armadilhas
usar inteiro sempre que possível (produto cruzado inteiro evita FP)
quando usar double: comparar com EPS; evitar divisão desnecessária
tratar casos especiais: segmentos degenerados (pontos idênticos), polígonos com poucos vértices, pontos colineares, retas verticais / horizontais
testar com muitos casos: colinearidade, pontos repetidos, bordas exatas, grande/saturação de inteiros (usar int64 se multiplicações grandes)
normalizar representação de reta para comparar igualdade (dividir por gcd ou fixar b)
0D — Pontos
representação: struct { double x, y; }
distância entre p e q: d = sqrt((px-qx)^2 + (py-qy)^2)
rotação CCW de θ em torno da origem: (x', y') = (xcosθ - ysinθ, xsinθ + ycosθ)
ordenar pontos: por x então y (ou por polar em relacionamentos com um pivot)
Dicas rápidas para competições
escreva/tenha um template com: Point struct, cross, dot, comparator, dist, orientation, segment intersection, polygon area, point-in-polygon, convex-hull
comece com funções robustas e testadas localmente
para precisão crítica, preferir algoritmos que usem apenas comparações e multiplicações inteiras
documente invariantes (ex.: pontos do polígono em CCW) no código
Notas do Capítulo
material derivado de fontes: Dr Cheng Holun, Alan (NUS), Igor Naverniouk (shygypsy)
capítulo cresceu muito desde a 1ª edição; ainda não cobre tudo para ICPC
técnicas avançadas não discutidas em detalhe aqui:
plane sweep
interseção de outros objetos geométricos
Closest Pair Problem (Divide & Conquer)
Furthest Pair Problem
Rotating Calipers
recomendação para preparação de ICPC:
dedique uma pessoa do time para dominar geometria
treine codificação robusta e casos degenerados
estude referências (ex.: KACTL, e-maxx, livros clássicos de geometria computacional)
Visão geral
0D/1D/2D/3D: foco em 2D para competições
Boas práticas: evitar FP quando possível; usar EPS = 1e-9; testar muitos casos extremos
Principais ferramentas: vetores, produto escalar, produto vetorial, transformações (rotação), equações de reta, polígonos, convex hull
Referências & leitura
shoelace formula, Heron, Graham scan, Andrew monotone chain, winding number vs ray casting
sugerido: testar bibliotecas de geometria de competições (kactl, e-maxx) para templates
Recursos & referências rápidas
shoelace formula, Heron, Graham scan, Andrew monotone chain, winding number, ray casting
templates recomendados: kactl, e-maxx.ru