Given n radio towers in a plane. What is the minimum length for them connecting each other by setting up cable lines? Two towers are connected, if there is a sequence of cable lines connecting together and ending at two towers.
There are multiple test cases in the plane. For each test case:
First line contains a number n (1<=n<=100000).
Next n lines there are two integers (x,y) per line indicating the location of each tower. The locations of all towers are pairwise different.
The distance between two towers is calculated by Euclidean distance.
All numbers will not larger than 10000, or less than -10000.
For each test case please output the minimum total cable lines' length, two numbers after decimal point.
3 0 0 0 3 4 3 7 0 0 0 1 0 2 0 3 0 4 0 5 0 6
7.00 6.00
Migrated from old NTUJ.
Tmt
| No. | Testdata Range | Score |
|---|