Geométricos

Textos a ler (são curtos!):

• Textos da Equipe de Harvard - Geometria 2D, Geometria 3D.
• Textos do Curso do Skiena - Grids, Princípios.
• Textos do Programming Challenges - Grids, Geometria, Geometria Computacional.
  • Cuidado que os códigos do Skiena são muito bons para competição e nem tão enxutos!!!!!

Outras referências:

• Livros
  • Introduction to Algorithms, Cormen, Leiserson, Rivest - Capítulo 35
  • Introduction to Algorithm - A Creative Approach, Udi Manber - Capítulo 8
• Aulas em áudio de Steven Skiena
  • Geometria: aula1, aula2.
  • Geometria Computacional: aula1, aula2.

Coisas a saber:

• Produto escalar e vetorial: pra que servem?, como calcular?
• Testar se dois segmentos se interceptam (interseção não vazia) ou se cruzam (não considerar os extremos)
• Pertinência de ponto em segmento. (teste exato)
• Distância de ponto a segmento
• Pertinência de ponto em polígono (convexo e caso geral)
• Convex Hull (Graham Scan)
• Par de pontos mais próximos (menos importante)

Exercícios a fazer, em ordem de importância:

• Problema D (Cruzamentos no Ar) da Maratona de Programação da USP 2002
• 109 - Scud Busters
• Problema E (Kryptonite Mine) da Regional Sulamericana 2003
• 10043 - Chainsaw Massacre