回分類題庫
d089: 2009 程式達人 C - 網路佈線問題
出處:

Difficulity : 2
Accepted : 19 Times | Submit :114 Times | Clicks : 1617
Accepted : 12 Users | Submit : 15 Users | Accepted rate : 80%
Time Limit :2001 ms | Memory Limit : 32001 KBytes
題目加入時間 : 2009-06-02 00:18

Content :

大仁分局的網路佈線圖被電腦怪客給竊取了,因此整個機房以及所有主機的架構和弱點也都被怪客給掌握了。然而,沒有破壞就沒有建設,因此財哥決定將整棟分局的網路線重新鋪設。


細心的財哥早就把分局內的所有網路設備的位置,都繪製在二維座標圖上。但由於哈佛市今年撥了過多的預算在財政部以及市容外貌整修上,因此大仁分局拿到的預算相當有限,連多餘的網路線都浪費不起。


大仁分局中,任意兩個設備可以透過筆直的網路線連接。財哥的首要目標是盡量節省網路線鋪設,但又必須把所有的設備連接在一起,避免浪費手頭上的預算。可是財哥最近相當的忙碌,他只好把這個專案丟給大家。


財哥已經幫大家把所有網路設備的座標都列出來了,請大家幫忙找出能滿足要求的網路佈線需要的最短長度是多少?

Input :

輸入的第一列為一個正整數,代表接下來有測試資料的組數。空一列之後開始輸入每組測資。

每組測試資料的第1列為一個整數n(0 < n <= 100),代表座標的個數。接下來的n列代表這n個點的座標,每列有2個實數。

輸入的第一列與第一組測試資料間空一列,各測試資料間亦空一列。

Output :

對每一組測試資料輸出需要網路線的最小長度是多少(四捨五入到小數第二位)。測試資料間亦請空一列。

Sample Input :

2
	
3
1.0 1.0
2.0 2.0
2.0 4.0

2
1.0 1.0
2.0 2.0

Sample Output :

3.41

1.41

Hint :


  

Author :


  Solve it!   Status Forum (0)

C++
C
JAVA
22335. david942j (24 ms , 516KB)
22336. david942j (26 ms , 520KB)
7287. pandia (48 ms , 4270KB)
46492. justin6 (64 ms , 528KB)
49614. CC501 (78 ms , 548KB)
7369. yuhanlyu (6 ms , 368KB)
21485. taop (12 ms , 380KB)
21473. onedie (14 ms , 384KB)
55527. ag100 (40 ms , 510KB)
55528. ag100 (58 ms , 506KB)
沒有解題記錄

執行時間會受很多因素影響因此僅供參考,主機等級請看這裡