a480. 導彈攔截系統 - 高中生程式解題系統

內容

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

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

為了簡單起見，城市位置以一點 $(ξ_{i}, η_{i})$ 來表示。

輸入說明

$x_{1}$ $y_{1}$

$x_{2}$ $y_{2}$

$n$

$ξ_{1}$ $η_{1}$

$ξ_{2}$ $η_{2}$

$⋮$

$ξ_{n}$ $η_{n}$

$1 \leq n \leq 10^{6}$ 。
$- 10^{4} \leq x_{1}, y_{1}, x_{2}, y_{2} \leq 10^{4}$ 。
對於所有的 $i \in {1, 2, \dots, n}$ ，均有 $- 10^{4} \leq ξ_{i}, η_{i} \leq 10^{4}$ 。
$(x_{1}, y_{1}) \neq (x_{2}, y_{2})$ 。
對於所有的 $i, j \in {1, 2, \dots, n}$ ，若 $i \neq j$ ，則 $(ξ_{i}, η_{i}) \neq (ξ_{j}, η_{j})$ 。
輸入的數皆為整數。

輸出說明

p

$p$ 為一整數，代表達成城市防護的能源消耗最小值。

範例輸入 #1

範例輸出 #1

測資資訊：

記憶體限制： 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 , <10M

提示：

將第一座導彈攔截系統的 $r$ 設為 $\sqrt{2}$ ，第二座導彈攔截系統的 $r$ 設為 $1$ ，即可得到能源消耗最小值 $3$ 。

標籤:

出處:

100學年度彰雲嘉區資訊學科能力競賽 [管理者： xavier13540 (柊四千) ]

編號	身分	題目	主題	人氣	發表日期
40042	xavier13540 (柊四千)	a480	作者提供的解法	313	2024-04-24 12:42