Estive fazendo umas contas e creio que posso ter chegado a uma resposta parcial.
Por uma quest�o de praticidade, numerei os v�rtices de A[0] at� A[n-1], no sentido
anti-hor�rio.
Tome o v�rtice A[0] e v� ligando com os outros v�rtices (A[1]; A[2]; ...; A[n-1]).
Note que cada diagonal A[0]A[i] divide o plano em dois semi-planos. Se o pol�gono �
convexo, podemos determinar exatamente quantos v�rtices ficam em cada semi-plano.
Para quem est� com a figura, � f�cil ver que, dada a diagonal A[0]A[i], todos os
pontos A[j] com 0<j<i est�o em um semi-plano e todos os pontos com i<j<n est�o em
outro semi-plano. Qualquer diagonal com v�rtices em semi-planos distintos ter� uma
intersec��o com a diagonal A[0]A[i].
Logo, cada diagonal possui SUM[i=1, n-1]{(i-1)(n-1-i)/2}
Leia-se "somat�rio de (i-1)(n-1-i)/2 quando i varia de 1 at� n-1"
Como s�o n diagonais, bastaria calcular n*SUM. Contudo, cada intersec��o est� sendo
contada duas vezes (uma para cada diagonal que a "produz"). Assim, o resultado seria
n*Sum/2.
Devo confessar que n�o terminei as contas do somat�rio pq estou meio cansado, mas
creio que esse seja o n�mero de intersec��es pedido. Aguardo coment�rios...
PROBLEMA:
(Admitindo que o valor encontrado antes esteja correto :-))
O n�mero encontrado antes N�O necessariamente � o n�mero de intersec��es DISTINTAS.
Pode-se afirmar com certeza que o n�mero de distintas � menor ou igual ao valor
calculado.
O problema agora �: Como descobrir quais intersec��es s�o m�ltiplas, isto �,
formadas por mais de 2 diagonais? E como cont�-las?
[]'s
Alexandre Tessarollo
--
__________________________________________________________
Sign-up for your own FREE Personalized E-mail at Mail.com
http://www.mail.com/?sr=signup
=========================================================================
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
O administrador desta lista � <[EMAIL PROTECTED]>
=========================================================================
