Roteiro 9

De DCC UFMG - Maratona de Programação
Ir para: navegação, pesquisa

< Voltar para: Roteiros | Roteiro 8

Introdução

Este roteiro busca introduzir as técnicas básicas para a resolução dos problemas computacionais de natureza geométrica. Apesar de simples, os conceitos abordados são fundamentais para resolver problemas mais complexos, que quase sempre podem ser simplificados através de observações sutis. É importante ressaltar que é raro encontrar problemas puramente geométricos nas competições. Eles normalmente são a "primeira camada" de um problema maior que envolva grafos ou programação dinâmica, por exemplo.

Materiais de apoio

Não existem muitas referências para este roteiro, dado que o conteúdo é visto no primeiro semestre do curso, e para a maioria será apenas uma revisão. Entretanto, é extremamente comum que implementações de algoritmos geométricos utilizem sobrecarga de operadores para as mais diversas finalidades, então estude este tópico se ainda não estiver confortável com ele.

Problemas

Lista de problemas para serem resolvidos. As soluções estão disponíveis, mas é recomendado que você não consulte antes de tentar resolver os problemas. Os problemas em negrito são mais difíceis, mas são mais importantes, porque ilustram melhor como os problemas geométricos aparecem em competições. Resolva pelo menos 7 problemas, incluindo os problemas em negrito. O problema em rosa é para aquecimento.

Roteiro 9
# Problema Link Online Judge Nível Observações
1 NLOGONIA Divisão da Nlogônia SPOJ-BR 0 Aquecimento
2 PARPROX Pontos SPOJ-BR 1 -
3 METEORO Meteoro SPOJ-BR 1 -
4 UVa 11505 Logo UVa 1 -
5 UVa 10210 Romeo and Juliet UVa 1 trigonometria
6 FUROS Furos SPOJ-BR 2 -
7 UVa 11227 The Silver Bullet UVa 2 colinearidade
8 UVa 10310 Dog and Gopher UVa 2 distância
9 UVa 10263 Railway UVa 3 distância ponto-reta
10 MONAMAZ Monitorando a Amazônia SPOJ-BR 3 geometria + busca
11 CAIXAMG Caixa de papelão SPOJ-BR 2 Volume máximo
12 Trace Trace Codeforces 1 Área
13 Where do I Turn? Where do I Turn? Codeforces 1 Pontos

Próximo roteiro

O próximo roteiro de treinamento tratará de Combinatória e Teoria dos Números. Recomendamos que você avance apenas depois de ler o material de apoio e ter feito, pelo menos, 7 problemas.

Link para o Roteiro 10

Ferramentas pessoais
Espaços nominais

Variantes
Ações
Navegação
Ferramentas