Re: [obm-l] um problema de contagem

["Nicolau C. Saldanha" <nicolau@xxxxxxxxxxxxxx>]

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.

> Não precisa pensar muito pra perceber que esse problema surgiu do 
> problema "Contar o numero de intersecoes das diagonais em poligono NÃO 
> regular" Eu já consegui achar quantas são as interseçoes de dentro e de 
> fora [n(n-1)(n-2)(n-3)/8] preciso tirar desse numero as interseções que 
> ocorrem fora para chegar na resposta desejada.
> 
> obs: Talvez existam outras formas de resolver o problema, mas no caso 
> estou particularmente interessado em saber como contar as interseções do 
> lado de fora da região poligonal.

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.
 
[]s, N.
=========================================================================
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
=========================================================================