TopCoder

User's AC Ratio

57.1% (4/7)

Submission's AC Ratio

11.5% (12/104)

Tags

Description

隨著每年選訓營打Dota AllStar的人越來越多,儘管師大進修推廣部十樓的交誼聽被施以某種力場而變大了,但再怎麼好的筆電還是需要網路線才能連線的(那裡的無線網路超爛)。當然,我們希望需要的網路線越短越好。

現在有N個人要打Dota AllStar(這是新版的地圖,最多可以容納100000人進行遊戲),因為每個人可能有各自的癖好、風水、或宗教信仰等問題,所以每個人都為自已選了一個最有利的位置,這個位置以平面上的座標點來表示。連接兩台筆電需要的最短網路線長度為兩台筆電間的直線距離,每台筆電所連接的網路線數量沒有限制。

問你將這N台筆電全部連在一起,最少需要多長的網路線。

Input Format

本題只有一組測資。

輸入檔第1行為一個數字N≤100000,代表總共有N個人。

接下來第2到第n+1行,每行包含兩個數(x,y)為這N個人所選的位置(0≤x,y≤10000)

Output Format

輸出將這N台筆電全部連在一起,最少需要多長的網路線。四捨五入到小數以下第2位。

Sample Input 1

5
0 0
0 2
2 0
2 2
1 1

Sample Output 1

5.66

Hints

本題測資修正,修正為僅有一組測資,N≤100000,時間限制做相應的調整。

Problem Source

原TIOJ1310 / [TIOJ] IOI2008 暖身賽 2(prob J)。Problem Setter:seanwu。

Subtasks

No. Testdata Range Score
1 0 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 10000 65536 262144 1