Pessoal,
Terminei de corrigir a P2, que foi de fato mais difícil que a fácil P1. Coloquei histogramas das notas das duas provas aqui:
http://www.ime.usp.br/~cris/geocomp/provas/hist.html
Assim você pode avaliar como está a sua performance em comparação com o restante da turma.
A última questão da P2 era a mais legal, tirada da lista, mas vários não a fizeram ou se enrolaram.
Um jeito de fazê-la era por um algoritmo de linha de varredura, que percorresse o Vor(P), por exemplo, de cima para baixo, com os seus vértices de pontos-evento, mantendo numa ABBB as arestas de Vor(P) ordenadas da esquerda para a direita. Antes de processar cada ponto-evento, armazenaríamos uma cópia da ABBB, para uso posterior nas buscas. Cada ABBB estaria associada ao ponto-evento, ou seja, ao vértice que iria modificá-la. Os vértices já teriam sido ordenados por Y-coordenadas no início, para a montagem da fila de eventos. Essa ordenação também seria guardada para uso nas buscas, tendo agora apontadores para cada uma dessas ABBBs, ao lado de cada vértice.
A busca então procederia em dois passos: primeiro uma busca binária simples no vetor de vértices de Vor(P), que está ordenado por Y-coordenada, usando como chave p_Y (a Y-coordenada do ponto a ser buscado). Digamos que p_Y está entre as Y-coordenadas dos vértices i-1 e i (os casos da ponta do vetor são levemente diferentes mas similares). Então procedemos com uma busca por p_X na ABBB correspondente ao vértice i. Lembre-se que nos nós dessa ABBB temos arestas. A decisão de ir para a esquerda ou direita na ABBB pode então ser feita através do predicado esquerda.
O tempo para construção da ED é O(n^2) (por conta da impressão da ABBB a cada ponto-evento), o espaço também é O(n^2). A busca é O(lg n).
Era isso...
Até breve!
Cris
Fórum