某個國家研發了一套導彈攔截系統,只要設定了防護半徑 r,在距離系統設置處 r 以內的範圍都會受到防護。此外,他們發現,啟用該系統會消耗大量的能源,且能源消耗為 r2。
在研發完成之際,敵國隨即向他們發射飛彈展開攻擊。不幸的是,該系統仍在試驗階段,所以目前僅設置於兩處 (x1, y1) 與 (x2, y2)。由於能源消耗過於龐大,要使防護持久就必須讓能源消耗越小越好。因此,他們希望能以最少的能源消耗下防護境內所有的 n 個城市。
為了簡單起見,城市位置以一點 (xi, yi) 來表示。
第一行有兩個整數 x1, y1,代表第一座導彈攔截系統的座標位置。
第二行也有兩個整數 x2, y2,代表第二座導彈攔截系統的座標位置。
第三行有一個正整數 n,其中 n ≦ 1,000,000,代表這個國家的城市個數。
接下來的 n 行,每行有兩的整數 xi, yi,代表輸入的第 i 個城市的座標位置。
輸入的座標 (x, y) 皆滿足 |x| ≦ 10,000 且 |y| ≦ 10,000。
0 0 0 2 4 0 3 1 -1 1 0 1 1
3
編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
沒有發現任何「解題報告」
|