a480. 導彈攔截系統
標籤 :
通過比率 : 196人/363人 ( 54% ) [非即時]
評分方式:
Strictly

最近更新 : 2024-04-22 16:51

內容

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

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

為了簡單起見,城市位置以一點 $\color{black}{(\xi_i, \eta_i)}$ 來表示。

輸入說明

$\color{black}{x_1}$ $\color{black}{y_1}$

$\color{black}{x_2}$ $\color{black}{y_2}$

$\color{black}{n}$

$\color{black}{\xi_1}$ $\color{black}{\eta_1}$

$\color{black}{\xi_2}$ $\color{black}{\eta_2}$

$\color{black}{\vdots}$

$\color{black}{\xi_n}$ $\color{black}{\eta_n}$

  • $\color{black}{1\le n\le10^6}$。
  • $\color{black}{-10^4\le x_1, y_1, x_2, y_2\le10^4}$。
  • 對於所有的 $\color{black}{i \in \{1, 2, \ldots, n\}}$,均有 $\color{black}{-10^4\le\xi_i, \eta_i\le10^4}$。
  • $\color{black}{(x_1, y_1)\ne(x_2, y_2)}$。
  • 對於所有的 $\color{black}{i, j \in \{1, 2, \ldots, n\}}$,若 $\color{black}{i\ne j}$,則 $\color{black}{(\xi_i, \eta_i)\ne(\xi_j, \eta_j)}$。
  • 輸入的數皆為整數。
輸出說明
$\color{black}{p}$
  • $\color{black}{p}$ 為一整數,代表達成城市防護的能源消耗最小值。
範例輸入 #1
0 0
0 2
4
0 3
1 -1
1 0
1 1
範例輸出 #1
3
測資資訊:
記憶體限制: 512 MB
提示 :

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

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

本題狀況 本題討論 排行

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