RE: Dúvida sobre fase de COMBINAR

[Jose Coelho de Pina <coelho@ime.usp.br>]

Paulo Eduardo Azevedo Silveira writes:
 > 
 > > Existem duas questões sobre este negocio de verificar x pontos. Uma coisa é
 > > mostra que é suficiente verificar x pontos. Para isto `basta' mostra que no
 > > retângulo de lados delta x 2 delta, sob determinadas condições, não cabem mais
 > > do que x (ou x+1) pontos. Outra coisa é mostrar que é necessári examinar os
 > > tais x pontos, para isto devemos mostrar um exemplo em que o algoritmo, por
 > > deixar de verificar o x-ésimo pontos, responde uma bobagem.
 > 
 > 
 > entao professor.
 > engracado que cabem 7 pontos!
 > entao a gente teria de verificar 6 pontos, porem eu fiz todos os casos
 > possiveis verificando 5 pontos e ele nao responde bobagem.
 > 
 > 
 >                   |
 >                   |
 >       5PL--------6PL----------7PR
 >       |           |            |
 >       |           |            |
 >       |           |            |
 >       |          4PR           |
 >       |           |            |
 >       |           |            |
 >       1PL--------2PL----------3PR
 >                   |
 >                   |
 > 
 > tipo, estamos verificando o 1pl, com certeza o 7pr nao mede menos de DEL
 > do 1pl, entao pra que verificar ele, mesmo ele cabendo no quadrinho?
 > 

Você tem toda a razão.

 > 
 > 
 > a mesma pergunta pode ser feita para o aso COM pontos coincidentes, tipo,
 > cabem 8 pontos no quadrinho, entao teoricamente voce tem de medir com os
 > outros 7, mas precisa mesmo? pois esse eh o pior caso, e esse caso voce na
 > precisa verificar o pessoal com os das pontas do outro lado, pq eles medem
 > DEL * raiz de 2. que eh maior que del.
 > 
 > nao entendo
 > o cormen viajou?

É isso ai. O exercício está um pouco equivocado. Acho que o exercício misturou
este negocio de cabem-x-pontos-no-retangulo com
é-necessário-calcularmos-x-distâncias.


 > 
 >  > 
 > > Legal esta coisas não ;-)
 > bacaninha
 > 

bacanão. ;-)

coelho