Geometria

Videoaulas

Aula 1

• Estruturas
• Polígonos

Aula 2

• Casco Convexo
• Linha de Varredura

Slides

Slides da aula 1

Slides da aula 2

Códigos e Materiais

Códigos da aula 1

• CSES Point Location Test
• CF Crazy Town
• CSES Polygon Area
• GCPC Hobbits

Códigos da aula 2

• CSES Convex Hull
• SPOJ Military Story
• CSES Restaurant Customers
• Line Intersection Problem
• ICPC 2019 Forests in Danger

Material extra

• [CP-algo] Basic Geometry
• [CP-algo] Finding area of simple polygon
• [CP-algo] Check if point belongs to the convex polygon
• [CF-Blog] Geometry: 2D points and lines
• [CF-Blog] Geometry: Polygon algorithms
• [CP-algo] Geometry: Convex Hull using Graham’s Scan
• [Wikipedia] Convex Hull using Monotone Chain
• [TopCoder] Sweep Line Algorithms
• [CF-Blog] How to sweep like a Sir
• [CP-algo] Sweep Line - Intersecting Segments
• [Summer School 2020] Geometria

Exercícios

Parte 1

• Exercícios de fixação
  • [CSES] Posição Ponto
  • [CF] Reta
  • [CSES] Área Polígono
  • [CF] Complexidade
  • [NERC 2020] Produto Vetorial
• Exercícios intermediários
  • [CF] Retas
  • [CF] Distância Euclidiana
  • [CF] Circunferência
  • [CF] Produto Vetorial 5D
  • [CF] Polígono
• Exercícios difíceis
  • [CF] Ordenação Angular
  • [Summer School 2018] Ponto dentro do Polígono (Busca Binária)
  • [CF] Complexidade
  • [GCPC 2018] Rotação 3D

Parte 2

• Exercícios de fixação
  • [CSES] Convex Hull
  • [SPOJ] Convex Hull
  • [CSES] Sweep Line
• Exercícios intermediários
  • [SPOJ] Convex Hull
  • [CF] Sweep Line + Combinatória
  • [SPOJ] Convex Hull - Combinação Linear
• Exercícios difíceis
  • [VIII Maratona UnB] - Convex Hull Combinação Linear
  • [ICPC - Nacional 2019] Geometria + Lazy Propagation
  • [SWERC 2018] Sweep Line Radial
  • [Timus] Sweep Line Segment Intersections