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 =========================================================================
