Abdul é um próspero caravanista,
proprietário de uma bela cáfila1 , no oásis de
Bahariya. Acabou de receber um carregamento de GPSes (instrumentos
muito importantes para todos os que viajam pelo deserto) e tem de o
levar para sul para o entregar ao seu primo Mohamed, trocando-o por um
carregamento das belas tâmaras que o primo trará do oásis de Farafra,
onde está estabelecido. Para tirar o melhor rendimento do negócio, as
duas caravanas, a de Abdul e a de Mohamed, deverão encontrar-se num
oásis intermédio, de maneira que o tempo de viagem seja o menor
possível. No deserto não há estradas e as caravanas podem descolar-se
em linha recta. No entanto, os camelos não aguentariam uma viagem
directa até ao oásis onde se fará a troca. Na verdade, devido às altas
temperaturas, os camelos têm de beber água pelo menos de cinco em
cinco dias, mais ou menos. Por outro lado, sabemos que os camelos no
deserto se deslocam à velocidade e 5km/h. Dadas as grandes distâncias
envolvidas, pode acontecer que as caravanas, deslocando-se uma de encontro à
outra, têm de parar em oásis intermédios, para os camelos se
dessedentarem.
Escreva um programa que, dada a lista de oásis, por meio das suas coordenadas (x,y), e o ponto de partida de cada caravana (é sempre um dos oásis), calcule o tempo mínimo necessário para as duas caravanas se encontrarem, num oásis intermédio, supondo que partem ao mesmo tempo. Por hipótese, as caravanas deslocam-se a 5 km/h e só param para os camelos beberem água, em oásis, ou para esperar pela outra, no oásis de encontro. Apesar de os camelos aguentarem mais, é contra a lei egípcia fazer um camelo andar mais de 100 km sem beber água. Sabemos que quando uma caravana pára para os camelos beberem água, a paragem dura uma hora. Logo a seguir, a marcha prossegue, até ao próximo oásis. Para efeitos deste problema, considere também que um oásis é um ponto de dimensão negligenciável (isto é, por exemplo, para nos deslocarmos de um oasis de coordenadas (0,10) para um de coordenadas (10,10), precisamos exactamente de 2h).
Na primeira linha vem um número N, o número de oásis (1 ≤ N ≤ 1000). Nas N linhas seguintes vêm dois números inteiros, representando as coordenadas (x,y) de cada um dos N oásis. A unidade corresponde a um quilómetro. O primeiro oásis representa o ponto de partida da primeira caravana (Abdul) e o último, o da segunda (Mohamed).
Uma única linha, na qual existe um único número, que representa o tempo mínimo necessário (em horas) para as duas caravanas se encontrarem, admitindo que ambas partem no mesmo instante. Este número deve ser escrito arredondado a duas casas decimais.
6 100 100 225 100 325 100 125 175 200 150 350 175
44.80
1Manada de bois, cardume de peixes, bando de pássaros, vara de porcos, cáfila de camelos.