a480: 導彈攔截系統
a480: 導彈攔截系統
題 目 :
某 個 國 家 研 發 了 一 套 導 彈 攔 截 系 統，只 要 設 定 了 防 護 半 徑 r，在 距 離 系 統 設置 處 r 以 內 的 範 圍 都 會 受 到 防 護。此 外，他 們 發 現，啟 用 該 系 統 會 消 耗 大 量 的 能 源，且 能 源 消 耗 為 r2。
在 研 發 完 成 之 際，敵 國 隨 即 向 他 們 發 射 飛 彈 展 開 攻 擊。不 幸 的 是，該 系 統 仍在 試 驗 階 段，所 以 目 前 僅 設 置 於 兩 處 (x1, y1) 與 (x2, y2)。由 於 能 源 消 耗 過 於 龐大，要 使 防 護 持 久 就 必 須 讓 能 源 消 耗 越 小 越 好。因 此，他 們 希 望 能 以 最 少 的能 源 消 耗 下 防 護 境 內 所 有 的 n 個 城 市。
為 了 簡 單 起 見，城 市 位 置 以 一 點 (xi, yi) 來 表 示。
solve:
城 市 對 於 第 一 個 防 禦 系 統 為 $d_1$，第 二 個 為 $d_2$，對 $d_1$ 做 排 序，然 後 窮舉 所 有 的 能 量 花 費。
如 果 第 一 個 系 統 所 能 包 含 最 遠 的 城 市 是 $c$，那 總 能 量 花 費 = $c$ 到 第 一 個 系 統 的 距 離 + 其 它 城 市 對 第 二 個 系 統 的 最 遠 距 離。
後 者 可 以 用 預 處 理 避 掉 時 間。
code:
在 研 發 完 成 之 際，敵 國 隨 即 向 他 們 發 射 飛 彈 展 開 攻 擊。不 幸 的 是，該 系 統 仍在 試 驗 階 段，所 以 目 前 僅 設 置 於 兩 處 (x1, y1) 與 (x2, y2)。由 於 能 源 消 耗 過 於 龐大，要 使 防 護 持 久 就 必 須 讓 能 源 消 耗 越 小 越 好。因 此，他 們 希 望 能 以 最 少 的能 源 消 耗 下 防 護 境 內 所 有 的 n 個 城 市。
為 了 簡 單 起 見，城 市 位 置 以 一 點 (xi, yi) 來 表 示。
solve:
城 市 對 於 第 一 個 防 禦 系 統 為 $d_1$，第 二 個 為 $d_2$，對 $d_1$ 做 排 序，然 後 窮舉 所 有 的 能 量 花 費。
如 果 第 一 個 系 統 所 能 包 含 最 遠 的 城 市 是 $c$，那 總 能 量 花 費 = $c$ 到 第 一 個 系 統 的 距 離 + 其 它 城 市 對 第 二 個 系 統 的 最 遠 距 離。
後 者 可 以 用 預 處 理 避 掉 時 間。
code:
留言
張貼留言