Problema C - Caravanas

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.

O Problema

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).

Input

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).

Output

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.

Exemplo de Input

6
100 100
225 100
325 100
125 175
200 150
350 175

Exemplo de Output

44.80

1Manada de bois, cardume de peixes, bando de pássaros, vara de porcos, cáfila de camelos.


Selecção dos Concorrentes Portugueses
Olimpíadas Internacionais de Informática 2008

(1 de Agosto de 2008)