Re: Dúvida sobre fase de COMBINAR

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

Oi Andrea

pensei tanto nesse exercico que ja nao sei mais nada, tipo, me perdi, sabe
qdo acontece isso?

                  |
                  |
      5PL--------6PL----------7PR
      |           |            |
      |           |            |
      |           |            |
      |          4PR           |
      |           |            |
      |           |            |
      2PL--------1PL----------3PR
                  |
                  |
        "reta do ponto-mediana"

pontos a esquerda(e nela) do ponto- mediana: 1PL, 2PL, 5PL, 6PL
ponto a direita do ponto-mediana: 3PR, 4PR, 7PR

os numeros indicam a ordenacao Y deles.
vamos analisar o caso de verificacao do ponto 1PL

Voce pode ver que esse caso pode existir, pois nenhum par de  pontos em L
dista menos que DEL, e nenhum par de pontos em R dista menos que del

sendo que DEl = min (delL, delR) {como visto em aula)

1PL e 4PR distam menos que DEL, porem eles estao em lados diferentes do
ponto mediana.

tipo
eh necessario verificar a distancia do 1PL com todos os outros pontos
desse retangulo?
creio que sim, mas ainda nao encontrei a explicacao, pois o 7PR eh o
ultimo na ordenacao e com certeza nao dista menos de DEL de 1pl
mas eh por ai o raciocinio
acho que so embaralhei mais.

socorro.


Paulo


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

On Tue, 3 Apr 2001, Dedinha wrote:

> Paulo,
> Eu sei que o Maqui Esperto n�o tem nada de esperto mas eu n�o consegui achar
> um caso que realmente eu preciso olhar os seis pontos,
> considerando que n�o h� pontos coincidentes.
> Como eu sempre percorro em ordem da coordenado y, se tiver um caso com PR na
> mediana tamb�m, esse vai ser no m�ximo o terceiro ponto a ser olhado e a� nem preciso olhar at� o sexto ponto.      
> E se n�o tiver o PR na mediana, ai preciso olhar no m�ximo 5 pontos.
> Sei l�, � isso
> Dea
> 
> ----- Original Message -----
> From: "Paulo Eduardo Azevedo Silveira" <peas@linux.ime.usp.br>
> To: <coelho-geocomp@ime.usp.br>
> Sent: Ter�a-feira, 3 de Abril de 2001 16:22
> Subject: Re: D�vida sobre fase de COMBINAR
> 
> 
> Oi Livio
> 2-)
> da 2, eh que voce pode ter a seguinte distribuicao que o professor Maqui
> Esperto nao pensou
> 
> PL         PL           PR
>            |
>            |
>            |
>            PR
>            |
>            |
> PL         PL           PR
>            |
>          "mediana"
> 
> isso eh, teremos no total 6 pontos para comparar
> PR - ponto do lado direito
> PL - ponto do lado esquerdo.
> 
> Eh muito comum a gente se enganar como o Maqui Esperto e pensar que o pior
> caso eh:
> 
> 
> PL         PL           PR
>            |
>            |
>            |
>            |
>            |
>            |
> PL         PL           PR
>            |
>          "mediana"
> 
> Porem podemos ter outro PR em cima da mediana.
> Paulo
> 
> 
> 
> 
> 
>