embrulho para presente

[Paulo Eduardo Azevedo Silveira <peas@linux.ime.usp.br>]

Oi pessoal

nao sei se vou conseguir a resposta ateh antes da prova, mas:

ja estou meio perdido nos nomes dos algoritmos do fecho convexo, sao
zilhares! mas o embrulho pra presente eu esqueci de vez!

ele tem de ser O(nh), entao para cada aresta devo fazer N comparacoes no
maximo. Ja tendo uma aresta do fecho, eu tenho de achar o ponto que tem
menor angulo polar com a aresta anterior, eu nao sei fazer isso!

ta ateh escrito la nas notas que era com o LEFT, o coleho mostrou na aula
mas eu nao lembro, o unico jeito que eu lembro eh testar as n arestar
remanecentes para saber se todos os outros pontos estao LEFT dessa aresta,
mas isso vai dar n^3, que eh o algoritmo anterior!

a pergunta: como uso o LEFT para descobrir o ponto que tem menor angulo em
relacao a uma dada aresta?
agora to pensando direito, e isso tambem eh usado no graham para o
pre-processamento.

paulo


Paulo Eduardo A. Silveira   <peas@linux.ime.usp.br>
UIN: 5142673   www.paulo.com.br

On Tue, 5 Jun 2001, Jose Coelho de Pina wrote:

> 
> Leandro Diullas Sperandio writes:
>  > Só para confirmar. Gostaria de saber se a matéria da prova é:
>  > 
>  > -6-Primitivas
>  > -8-Intersecção de Segmentos
>  > -9-Algoritmos para partição de Polígonos
>  > -10-Fecho Convexo Planar
> 
> É isso ai.
> 
> coelho
>