Nicolau C. Saldanha wrote:
On Sat, Feb 28, 2004 at 02:53:50PM -0300, niski wrote:<SNIP>
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.
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 =========================================================================
