k933. 10397 - Connect the Campus
Tags :
Accepted rate : 6人/7人 ( 86% ) [非即時]
評分方式:
Tolerant

最近更新 : 2024-05-27 15:37

Content

滑鐵盧大學校園內正在建設許多新建築。 該大學聘請了各種水電工和一名程式設計師。 
程式設計師被雇用來確保每棟建築通過校園通信電纜網絡(直接或間接)連接到其他每棟建築。
我們將每個建築物視為由 x 坐標和 y 坐標指定的點。 每條通信電纜恰好連接兩座建築物,沿著建築物之間的直線。信息沿著電纜雙向傳輸。 電纜可以自由交叉,但它們僅在端點(建築物內)連接在一起。
您已獲得一張校園地圖,其中顯示了所有建築物和現有通信電纜的位置。 您不得更改現有電纜。 確定在哪里安裝新的通信電纜,以便所有建築物都連接起來。 滑鐵盧大學希望您盡量減少使用的新電纜的數量。

Input

輸入包含多組測試資料
每組測試資料的第一行包含建築物數量 N (1 ≤ N ≤ 750)。建築物從 1 到 N 進行標記。

接下來的 N 行給出建築物的 x 和 y 坐標。 這些坐標是絕對值最大為 10000 的整數。沒有兩座建築物佔據同一點。

之後有一行包含現有電纜的數量 M (0 ≤ M ≤ 1000)。

後面是描述現有電纜的 M 行。

每根電纜由兩個整數表示:代表電纜直接連接的建築物編號。 最多有一根電纜直接連接每對建築物。

Output

對於每組測試資料,請輸出計劃使用的新電纜的總長度,四捨五入到小數點後兩位。

Sample Input #1
4
103 104
104 100
104 103
100 100
1
4 2
4
103 104
104 100
104 103
100 100
1
4 2
Sample Output #1
4.41
4.41
測資資訊:
記憶體限制: 64 MB
公開 測資點#0 (50%): 1.0s , <1K
公開 測資點#1 (50%): 1.0s , <1M
Hint :
Tags:
出處:
UVA [管理者: ig99lp33lp33 (위즈원) ]

Status Forum 排行

ID User Problem Subject Hit Post Date
沒有發現任何「解題報告」