Resolução Computacional do Ponto de Fermat - Project Euler 143

Problema 143 - Ponto de Fermat, Triângulo de Torricelli – 65%

        O ponto de Torricelli, consiste em localizar a posição otimizada entre três pontos, ou três vértices de triângulos. O desenho abaixo exemplifica a situação matemática.

[pic 1][pic 2]

        Basicamente o ponto de Torricelli é a localidade em que a somatória das distâncias P, Q, R é mínima, e o problema pede para que somamos os resultados de

( p + q + r )de triângulos de Torricelli, em que p + q + r ≤ 120000.

É possível provar o ponto de Torricelli por vários métodos, como modelos físicos com pêndulos, em que ao soltar os três pesos, a configuração do sistema estabiliza em P, aonde a energia potencial do sistema é mínima, uma vez que depende da altura dos pesos.

[pic 3]

É possível também obter a posição do ponto desenhando as três circunferências que circunscrevem os triângulos, como na primeira figura.

Também é possível encontrar o ponto, usando desenho geométrico, se tivermos o triângulo, ABC,

[pic 4]

é possível aplicar o rotacional do ponto B em relação ao ponto A em 60°,criando o ponto A’, fazendo o processo análogo a todos os pontos, e ligando-os formando triângulos equiláteros, teremos a seguinte configuração geométrica.

[pic 5]

Ao ligar os pontos extremos A’, B’, C’, respectivamente nos pontos, C, A, B, que são os opostos, a intersecção das retas, coincide com o ponto que as distâncias, p, q, r são mínimas, logo, o ponto encontrado é o ponto de Torricelli.

[pic 6]

Mas como a condição imposta para o exercício é extremamente trabalhosa, torna-se necessário, uma maneira algébrica para resolução do problema, pois a quantidade de checagens seria da ordem de 106, e anteriormente a ordem era de .[pic 7]

Elaborando o algoritmo do problema

        Admitindo que os ângulos centrais são todos 120° por trigonometria (ALFINIO,2014), calculamos por lei dos cossenos os lados do triângulo, logo,

[pic 8]

[pic 9]

[pic 10]

[pic 11]

Note que como limitante geométrica do problema, podemos generalizar a condição calculada para os outros lados, e para todos os triângulos de Torricelli, logo,

.[pic 12]

        Podemos chamar , de par (ALFINIO,2014), se for cumprido a condição acima, e ela for numericamente igual a um quadrado perfeito. Note que para que tenhamos triângulos de Torricelli, será necessário que , satisfaçam a condição de par, logo podemos listar alguns passos do algoritmo.[pic 13][pic 14]

1. Calcular todos os pares (condição imposta), em que ;[pic 15]
2. Classificar e organizar todos os pares registrados e nomeá-los (vetor);
3. Para cada par encontrado, comparar com outros dois, e identificar se eles cumprem a condição de triângulo de Torricelli;
4. Ao encontrar um trio que corresponda as condições, e que sua soma seja menor ou igual a 120000, condição essa, imposta pelo exercício, pode-se utilizar um Array, ou vetor, para sequenciar os trios, e somá-los.
5. Somar todas as somas encontradas baseadas nas condições impostas, e imprimir na tela o valor.

        Note que se trabalharmos com a equação acima, teremos de analisar  números. O que é possível, mas extremamente demorado extremamente custoso computacionalmente. Logo parametrizaremos a condição de par, ou seja,[pic 16]