URI Online Judge | 2522

FNDI's Network

By Ricardo Oliveira, UFPR BR Brazil

Timelimit: 1

The building of the Federal Department of Natural Islands (FDNI) is being widely reformed. Because of that, the old computer lab was destroyed, and a new one is being built on the second floor of the building.

There are N computers in the new lab, numbered from 1 to N. For each computer i, 1 ≤ iN, we know the position (xi, yi) at which it is installed. Now, it is needed to build the network that will connect the computers in the lab. To do so, it is possible to plug network cables between pairs of computers. To make the network valid, the cables should connect the computers in such a way that it is possible to send a message from any computer to any other computer in the lab, using one or more cables. The following figure exemplifies a possible configuration of a valid network:

Your task is, given the positions of each computer in the new lab, determine the minimum total length of cable needed to build a valid network.


First line of each test case contains an integer N (1 ≤ N ≤ 500), the number of computers in the lab. Each of the next N lines contains two integers xi and yi (1 ≤ xi, yi ≤ 104), indicating the position of a computer. There are no two computers at the same position.

The input ends with end-of-file (EOF).


For each test case, print a single line containing the minimum total length of cable needed to build a valid network. Round and print the answer with exactly two decimal places.

Input Sample Output Sample

1 1
5 1
1 5
5 5