Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

INTERLMG - Interligando a Sildávia

Uma das grandes vantagens da Internet é que ela permite comunicação em longa distância a custo baixíssimo. De fato, é provável que a maioria dos serviços que você acessa via Internet sejam providos por servidores a milhares de quilômetros da sua casa.

Os habitantes da Sildávia, porém, são estranhos. Eles não gostam de se comunicar com o restante do mundo, e limitam essas comunicações ao mínimo necessário. Na verdade, eles nem gostam muito de se comunicar com o restante do país: preferem estar em contato apenas com os seus vizinhos mais próximos, tanto quanto for possível.

O governo do país resolveu levar isso em conta na hora de projetar a nova rede de fibra ótica que interligará todas as cidades. Será escolhida uma distância d e para todo par de cidades tal que a distância entre elas é menor ou igual a d construir-se-á um canal de fibra ótica direto entre essas cidades.

Se d for muito grande, toda cidade será ligada diretamente a toda outra cidade, o que é caro. Se d for muito pequeno, porém, podem haver pares de cidades que não conseguem se comunicar nem de forma indireta (passando por outras cidades intermediárias) --- e, por mais que os Sildavianos não gostem de se comunicar com pessoas distantes, às vezes isso é necessário. Sua tarefa é escolher o menor valor possível para d tal que entre qualquer par de cidades haja um caminho de comunicação direto ou indireto entre elas.

Observações

  • A distância entre duas cidades c1 e c2 de coordenadas (x1, y1) e (x2, y2) é dada por dist(c1, c2) = sqrt((x1-x2)^2 + (y1-y2)^2)

Entrada

A entrada contém múltiplos casos de teste. A primeira linha de cada caso de teste contém um inteiro N (1 ≤ N ≤ 1000), o número de cidades. Em seguida, há N linhas, uma para cada cidade. Cada uma dessas linhas contém dois números de ponto flutuante, respectivamente as coordenadas x e y daquela cidade -104 ≤ x, y ≤ 104.

A entrada termina com N=0, que não deve ser processado.

Saída

Para cada caso de teste, imprima o menor valor para d que garante que há caminho entre qualquer par de cidades, com 4 casas decimais de precisão.

Exemplos

Entrada:
1
-3.141593 -9767.310900
0

Saída:
0.0000

Com apenas uma cidade, não é preciso ligar ninguém. Logo, d=0.0 é o suficiente.

Entrada:
2
-10000 10000
10000 -10000
0

Saída:
28284.2712

Com duas cidades, basta ligar uma diretamente à outra.

Entrada:
6
865.254068 -2211.194707
-2467.207937 3583.111316
3084.170032 451.830978
1869.357099 -1173.686944
-3558.188416 -3661.772167
1994.331312 -2935.253819
0

Saída:
6373.5951

Adicionado por:Wanderley Guimarăes
Data:2012-03-14
Tempo limite:1.095s
Tamanho do fonte:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Linguagem permitida:Todas exceto: ASM64 CLOJURE ERL FSHARP PERL6 PY_NBC SCALA TCL
Origem:Seletiva UFMG 2011

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.