SPOJ Brasil

Autor: Juarez Paulino

MEu Tio ALdo é proprietário de uma grande plantação de pequi no centro do país. Recentemente uma nova praga de nome científico axe rebolations surgiu e têm se proliferado em meio a plantação, causando uma queda brusca na produção do fruto. Muito se pensou em como controlar a praga, mas nenhuma das técnicas habituais foram eficazes. A situação ficou crítica, principalmente após a época de carnaval quando a reprodução da praga se mostrou excessivamente acelerada.

Felizmente os cientistas descobriram que a praga se torna inofensiva quando há um número reduzido de indivíduos. Com o embasamento científico e procurando uma solução eficiente para o problema, MEu Tio ALdo foi à uma fazenda vizinha de um velho amigo seu dedicada a produção de armas e rosas e solicitou a construção de uma bomba explosiva. A ideia é explodir a praga eliminando uma quantidade mínima M sobre o total N da população de axe rebolations. Quando a bomba é atirada ao solo em uma posição P(x, y) tudo que está a um raio R de distância de P é instantaneamente reduzido a pó (inclusive sob o círculo de ação). Porém o custo de construção da bomba é relacionada diretamente com o seu raio R de ação.

MEu Tio ALdo tem certeza que sua solução será eficaz mas agora ele quer gastar o mínimo possível com a construção da bomba. Dado o número total N da população de axe rebolations, a posição de cada indivíduo e o número mínimo M da população que precisa ser dizimada, calcule o raio mínimo da bomba que MEu Tio ALdo pretende construir.

Entrada

A entrada contém vários casos de teste. A primeira linha de um caso de teste contém dois números inteiros N e M (2 ≤ M ≤ N ≤ 200), representando o número total e a quantidade mínima de indivíduos axe rebolation que se deve eliminar para controlar a praga. Cada uma das N linhas seguintes contém dois inteiros X e Y , separados por um espaço em branco (| X|,| Y| ≤ 10000), indicando a localização de um indíviduo.

O final da entrada é indicado por uma linha seguida de dois 0's e não deverá ser processada.

Os dados devem ser lidos da entrada padrão.

Saída

Para cada caso de teste da entrada seu programa deve imprimir uma única linha, contendo um número real, escrito com precisão de três casas decimais, indicando o raio mínimo de cobertura da bomba que MEu Tio ALdo deve construir para eliminar pelo menos M axe rebolations.

O resultado de seu programa deve ser escrito na saída padrão.

Exemplo

Entrada:
4 3
2 3
5 -2
-2 -1
-1 4

4 3
0 0
1 1
-1 -1
10000 10000

4 2
-10000 -10000
-10000 10000
10000 -10000
10000 10000

0 0


Saída:
2.850
1.414
10000.000

Nota: No primeiro caso podemos formar 4 círculos mínimos que cobrem 3 pontos: C1(P1, P2, P3) com R1 = 3.644; C2(P1, P2, P4) com R2 = 4.243; C3(P1, P3, P4) com R3 = 2.850 e C4(P2, P3, P4) com R4 = 4.249. Tomamos como resposta o menor raio R3.