a480. 導彈攔截系統
Tags :
Accepted rate : 193人/357人 ( 54% ) [非即時]
評分方式:
Strictly

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

Content

某個國家研發了一套導彈攔截系統,只要設定了防護半徑 $\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)}$ 來表示。

Input

$\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)}$。
  • 輸入的數皆為整數。
Output
$\color{black}{p}$
  • $\color{black}{p}$ 為一整數,代表達成城市防護的能源消耗最小值。
Sample Input #1
0 0
0 2
4
0 3
1 -1
1 0
1 1
Sample Output #1
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 , <10M
Hint :

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

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

Status Forum 排行

ID User Problem Subject Hit Post Date
40042 xavier13540 (柊 四千) a480
作者提供的解法
175 2024-04-24 12:42