Descrição
O professor de Matemática do Zequinha propôs um desafio à classe. Entregou um papel quadriculado com vários pontos marcados e agora os alunos precisam interligar todos eles com segmentos de reta, desde que não produzam ciclos, ou seja, não podem formar polígonos fechados com os segmentos de reta. Ganha o desafio aquele que interligar todos os pontos perfazendo o menor comprimento total das retas.
Você, tio do Zequinha, foi então desafiado pelo próprio sobrinho a calcular o menor valor e assim ajudá-lo a vencer o desafio.
Entrada
Um valor N (0<=N<1000) é informado inicialmente, indicando a quantidade de casos de teste a serem avaliados. Cada caso de teste inicia-se com um inteiro P (2<=P<=50) representando a quantidade de pontos marcados no plano cartesiano. Em seguida, tem-se P linhas contendo dois números inteiros Xa e Ya (-1000<=Xa, Ya <= 1000) descrevendo a localização de um ponto em termos de suas coordenadas, onde Xa é a abscissa (eixo x) e Ya é a ordenada (eixo y). Um espaço em branco separa dois inteiros na mesma linha da entrada.
Saída
Para cada caso de teste imprima a distância mínima com que todos os pontos podem ser interligados sem formar ciclos. Use tipo real de precisão dupla para tratar a distância entre os pontos. A distância total deverá ser exibida com 4 casas depois da vírgula.
| Exemplos de Entrada | Exemplos de Saída |
|---|---|
|
2 |
11.8482 |
Efetue Login ou Cadastre-se para submeter uma solução.
Criado por Antonio Cesar de Barros Munari (Fatec Sorocaba) | Adaptado por erich.rodriguesf | Competição: Interfatecs 2014 2ª fase