Roteiro 14

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

< Voltar para: Roteiros | Roteiro 13

Introdução

Começaremos a tratar neste roteiro dos problemas mais relevantes de Geometria Computacional. É essencial que os conceitos tratado no Roteiro 9 estejam consolidados. Serão três assuntos abordados: convex hulls, polígonos e circunferências. Não subestime problemas com circunferências, pois eles são relativamente frequentes e podem ser mais difíceis do que parecem. É importante ressaltar, mais uma vez, que os problemas geométricos nem sempre aparecem sozinhos. Esteja preparado para resolver dois problemas em um.

Materiais de apoio

Problemas

Lista de problemas para serem resolvidos. A única dificuldade de todos os problemas listados é encontrar a função/estrutura de dados certa implementada na STL que torna o problema fácil de ser implementado. Ainda assim, a solução está disponível, mas recomendamos que não a consulte antes de tentar o bastante. Dê uma olhada na referência passada nos materiais de apoio deste roteiro para encontrar o que você procura. Os problemas em negrito são os mais importantes deste roteiro. Recomendamos que resolva um total de, no mínimo, 7 dos problemas abaixo, incluindo os em negrito.

Roteiro 14
# Problema Link Online Judge Nível Observações
1 HANGOVER Hangover SPOJ 1 Aquecimento - Simular a soma dos elementos
2 LINESEG Intersection SPOJ 1 Aquecimento - intercessão simples de segmentos
3 ELEVADOR Elevador SPOJ-BR 2 ver abaixo [*]
4 DVORONOI Diagrama de Voronoi SPOJ-BR 3 volume de sólido
5 UVa 10065 Useless Tile Packers UVa 3 convex hull e área de polígono
6 UVa 10221 Satellites UVa 2 -
7 UVa 11152 Colorful Flowers UVa 3 -
8 UVa_478 Points in Figures: Rectangles, Circles, Triangles UVa 2 Intercessão entre ponto e sólido
9 CANUBIS Canhões de Anúbis SPOJ-BR 3 coplanaridade
10 CEBOLA Cebola SPOJ-BR 3 convex hull
11 UVa 10075 Airlines UVa 3 esfera e caminho mínimo
12 CERCAMG Cercadinho de Plantas SPOJ-BR 2 convex hull

[*] O código fonte deste problema está disponível no site da maratona, mas confiamos que você não trapaceará.

Próximo roteiro

O Roteiro 15 encerrará este primeiro conjunto de roteiros, abordando temas diversos para revisar o que foi aprendido.

Link para o Roteiro 15

Ferramentas pessoais
Espaços nominais

Variantes
Ações
Navegação
Ferramentas