a480: 導彈攔截系統
Tags :
Accepted rate : 87人/126人 ( 69% ) [非即時]
評分方式:
Tolerant

最近更新 : 2013-03-21 16:29

Content

某個國家研發了一套導彈攔截系統,只要設定了防護半徑 r,在距離系統設置處 r 以內的範圍都會受到防護。此外,他們發現,啟用該系統會消耗大量的能源,且能源消耗為 r2

在研發完成之際,敵國隨即向他們發射飛彈展開攻擊。不幸的是,該系統仍在試驗階段,所以目前僅設置於兩處 (x1, y1) 與 (x2, y2)。由於能源消耗過於龐大,要使防護持久就必須讓能源消耗越小越好。因此,他們希望能以最少的能源消耗下防護境內所有的 n 個城市。

為了簡單起見,城市位置以一點 (xi, yi) 來表示。

Input

第一行有兩個整數 x1, y1,代表第一座導彈攔截系統的座標位置。

第二行也有兩個整數 x2, y2,代表第二座導彈攔截系統的座標位置。 

第三行有一個正整數 n,其中 n ≦ 1,000,000,代表這個國家的城市個數。

接下來的 n 行,每行有兩的整數 xi, yi,代表輸入的第 i 個城市的座標位置。

輸入的座標 (x, y) 皆滿足 |x| ≦ 10,000 且 |y| ≦ 10,000。

Output
請輸出一個正整數 p,代表達成城市防護的能源消耗最小值。
Sample Input
0 0
0 2
4
0 3
1 -1
1 0
1 1
Sample Output
3
測資資訊:
記憶體限制: 512 MB
不公開 測資點#0 (20%): 1.0s , <1K
不公開 測資點#1 (20%): 1.0s , <1M
不公開 測資點#2 (20%): 1.0s , <10M
不公開 測資點#3 (20%): 1.0s , <50M
不公開 測資點#4 (20%): 1.0s , <50M
Hint :
將第一座導彈攔截系統的 r 設為 √(2),第二座導彈攔截系統的 r 設為 1,即可得到能源消耗最小值 3。
Tags:
出處:
100學年度彰雲嘉區資訊學科能力競賽 [管理者:
xavier13540 (柊 四千)
]


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