滑鐵盧大學校園內正在建設許多新建築。 該大學聘請了各種水電工和一名程式設計師。
程式設計師被雇用來確保每棟建築通過校園通信電纜網絡（直接或間接）連接到其他每棟建築。
我們將每個建築物視為由 x 坐標和 y 坐標指定的點。 每條通信電纜恰好連接兩座建築物，沿著建築物之間的直線。信息沿著電纜雙向傳輸。 電纜可以自由交叉，但它們僅在端點（建築物內）連接在一起。
您已獲得一張校園地圖，其中顯示了所有建築物和現有通信電纜的位置。 您不得更改現有電纜。 確定在哪里安裝新的通信電纜，以便所有建築物都連接起來。 滑鐵盧大學希望您盡量減少使用的新電纜的數量。
輸入包含多組測試資料
每組測試資料的第一行包含建築物數量 N (1 ≤ N ≤ 750)。建築物從 1 到 N 進行標記。
接下來的 N 行給出建築物的 x 和 y 坐標。 這些坐標是絕對值最大為 10000 的整數。沒有兩座建築物佔據同一點。
之後有一行包含現有電纜的數量 M (0 ≤ M ≤ 1000)。
後面是描述現有電纜的 M 行。
每根電纜由兩個整數表示：代表電纜直接連接的建築物編號。 最多有一根電纜直接連接每對建築物。
對於每組測試資料，請輸出計劃使用的新電纜的總長度，四捨五入到小數點後兩位。
4 103 104 104 100 104 103 100 100 1 4 2 4 103 104 104 100 104 103 100 100 1 4 2
4.41 4.41
| 編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
|
沒有發現任何「解題報告」
|
|||||