[obm-l] Re: CRUEL

["Alexandre Tessarollo" <tessa@xxxxxxxx>]

   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 é <nicolau@mat.puc-rio.br>
=========================================================================