Re: [obm-l] um problema de contagem

[niski <fabio@xxxxxxxxx>]

Nicolau C. Saldanha wrote:

> On Sat, Feb 28, 2004 at 02:53:50PM -0300, niski wrote:
> 
>>Considere n pontos no plano nunca 3 em linha reta. Esses pontos 
>>determinam uma região poligonal. Qual é o numero de interseções das 
>>retas determinadas por esses pontos FORA da região poligonal.
> 
<SNIP>
> 
> Se eu bem entendi você quer que os n pontos sejam os vértices
> de um polígono convexo. Acho que você também quer supor
> que dois pares de pontos nunca determinam retas paralelas.
> Se for isso, observe que dados 4 dos n pontos (digamos A, B, C, D,
> no sentido antihorário), existe sempre uma interseção dentro
> (AC x BD, a interseção entre as retas AC e BD) e duas fora (AB x CD, AD x BC).
> Junte esta observação com a sua e você resolve os dois problemas.

Vou pensar na sua observação, mas não entendi sobre a condição imposta a 
respeito do paralelismo dos lados do poligono. A unica restrição que o 
enunciado do problema faz é que o poligono não seja regular e é possivel 
que essa condicão seja satisfeita mesmo em um poligono com dois lados 
não parelelos certo? um trapézio isósceles por exemplo. Ou voce quer 
dizer que podemos considerar sem perda de generalidade o poligono com 
nenhum lado paralelo?

-- 
Niski - http://www.linux.ime.usp.br/~niski

"When we ask advice, we are usually looking for an accomplice."
Joseph Louis LaGrange

=========================================================================
Instruções para entrar na lista, sair da lista e usar a lista em
http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html
=========================================================================