Você pode assumir que os vértices do polígono têm coordenadas inteiras, e trabalhar o tempo todo apenas com inteiros.
Você deve considerar o caso em que há pontos do polígono com y-coordenadas iguais. Para tratar esse caso, você apenas precisa estabelecer que um ponto p "vem antes" de um ponto q se p_y > q_y ou (p_y = q_y e p_x < q_x), ou seja, se o ponto p está mais acima de q ou se está na mesma linha, porém mais à esquerda. A determinação de se as arestas de p estão para cima ou para baixo de p deve ser consistente com essa ordem.
Você pode usar skip lists ou alguma das várias ABBB (AVL, Rubro-Negra, árvores 2-3, B-árvores). Para informações sobre skip lists, consulte a seção 13.5 do Sedgewick. Para uma olhada rápida em alguns dos algoritmos de skip lists, veja as seguintes transparências [pdf] [ps.gz]. Árvores rubro-negras são apresentadas no capítulo 13 do CLRS, enquanto que B-árvores aparecem no capítulo 18 do CLRS. Se o código para a ED que você decidir usar não tiver sido feito por você, escreva num comentário no seu programa de onde você obteve o código e quem é o autor dele, dando assim os devidos créditos ao autor.
Valendo bônus: a implementação do algoritmo O(n lg n) para triangularização de um polígono arbitrário com n vértices (ou seja, a composição desse algoritmo com o que triangulariza polígonos monótonos).
Data de entrega: 7 de outubro (domingo)
Os dados de entrada para esse problema consistem de vários casos de testes. A primeira linha do arquivo de entrada contém um inteiro N, que é o número de casos de teste. Em cada caso de teste são dados um poliedro convexo, através da ED arestas aladas, um inteiro positivo t e as coordenadas de t pontos.
Para cada um dos t pontos, seu programa deve imprimir uma linha, dizendo se o ponto pertence ou não ao poliedro. A saída de diferentes casos de teste devem ser separadas por uma linha em branco.
Você pode supor que as coordenadas de todos os pontos dados são inteiras e que as faces dos poliedros são todas triangulares.
Os dados da ED arestas aladas seguem o seguinte padrão. Na primeira linha, são dados três números, n, m, e f. Estes números correspondem ao número de vértices, arestas e faces do poliedro respectivamente. Considera-se que os vértices do poliedro estão numerados de 0 a n-1, as arestas são numeradas de 0 a m-1 e as faces, de 0 a f-1. Depois dessa primeira linha, seguem n linhas, cada uma correspondendo a um dos vértices. Especificamente, para i=0,...,n-1, a linha 1+i contem as coordenadas x, y e z do vértice i seguidas do valor de av[i]. Nas próximas linhas, vem o valor de af[i], para i=0,...,f-1. Nas m próximas linhas, vem os valores de v1[i], v2[i], fccw[i], fcw[i], pccw[i], nccw[i], pcw[i], ncw[i], para i=0,...,m-1.
A leitura deve ser feita da entrada padrão, como nos programas
submetidos ao UVA, e a saída também deve ser para a saída padrão,
conforme a descrição acima. Veja aqui um exemplo
de arquivo de entrada. A saída esperada para esse arquivo é
Essa entrada consiste de dois casos de teste: o tetraedro com
vértices (0,0,0), (0,0,10), (0,10,0) e (10,0,0), e o cubo com vértices
(0,0,0), (0,0,10), (0,10,0), (10,0,0), (0,10,10), (10,10,0), (10,0,10)
e (10,10,10). O cubo tem cada uma de suas faces quadradas dividida em
dois triângulos, para satisfazer o enunciado. Confira!
Bônus: Implemente o algoritmo do embrulho para
presente para calcular o fecho convexo 3D de um conjunto de pontos dados
do R3. O bônus valerá como uma nota extra de
tarefa.
Prazo de entrega: 2 de dezembro para a
tarefa, e 7 de dezembro para o bônus.
Qualquer dúvida, me escreva!
O ponto (1, 1, 1) pertence ao poliedro.
O ponto (10, 10, 10) nao pertence ao poliedro.
O ponto (1, 1, 1) pertence ao poliedro.
O ponto (20, 20, 20) nao pertence ao poliedro.
O ponto (20, 0, 0) nao pertence ao poliedro.
O ponto (0, 0, 0) pertence ao poliedro.
O ponto (-1, 0, 0) nao pertence ao poliedro.
O ponto (0, 2, 0) pertence ao poliedro.