[ZJ][sort] a480. 導彈攔截系統＠Morris' Blog

2012-09-16 12:14:06| 人氣2,007| 回應0 | 上一篇 | 下一篇

[ZJ][sort] a480. 導彈攔截系統

推薦 0 收藏 0 轉貼0 訂閱站台

內容：

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

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

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

輸入說明：

第一行有兩個整數 x₁, y₁，代表第一座導彈攔截系統的座標位置。

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

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

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

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

輸出說明：

請輸出一個正整數 p，代表達成城市防護的能源消耗最小值。

範例輸入：

範例輸出：

提示：

將第一座導彈攔截系統的 r 設為 √(2)，第二座導彈攔截系統的 r 設為 1，即可得到能源消耗最小值 3。

出處：

100 彰雲嘉區學科能力競賽資訊科 (管理：xavier13540)

對第一位置的距離, 對第二位置的距離 ->(a, b)

先為 a 做升排序

之後窮舉 p = D[i].a + max(D[i+k].b) 1 <= k
ANSI C 的排序比較慢, 所以貼 C++ 的

#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
#define max(x,y) ((x)>(y)?(x):(y))
using namespace std;
typedef struct {
    int a, b;
} E;
E D[1000005];
bool cmp(E i, E j) {
    return i.a < j.a;
}
int main() {
    int x1, x2, y1, y2, x, y;
    int n, i, j;
    while(scanf("%d %d %d %d", &x1, &y1, &x2, &y2) == 4) {
        scanf("%d", &n);
        for(i = 0; i < n; i++) {
            scanf("%d %d", &x, &y);
            D[i].a = (x-x1)*(x-x1)+(y-y1)*(y-y1);
            D[i].b = (x-x2)*(x-x2)+(y-y2)*(y-y2);
        }
        sort(D, D+n, cmp);
        for(i = n-2; i >= 0; i--)
            D[i].b = max(D[i].b, D[i+1].b);
        int ans = 2147483647;
        for(i = 0; i < n; i++) {
            int p = D[i].a;
            int tmp = 0;
            if(i != n-1)    tmp = D[i+1].b;
            p = D[i].a + tmp;
            ans = ans < p ? ans : p;
        }
        ans = ans < D[0].b ? ans : D[0].b;
        printf("%d\n", ans);
    }
    return 0;
}

我要檢舉

#a480#導彈攔截系統

台長： Morris

您可能對以下文章有興趣

b067. 6. 下棋問題

d887. 1.山脈種類(chain)

b058. 3. 關鍵邏輯閘

[ZJ][數學解] a534. IOI2008 Day2.1.花園問題

人氣(2,007) | 回應(0)| 推薦 (0)| 收藏 (0)| 轉寄
全站分類: 不分類 | 個人分類: 資訊競賽 |
此分類下一篇:[ZJ][一年後修裝版][C++] b113. 6. 線性系統求解
此分類上一篇:[ZJ][背包問題+Greedy] a455. TOI2010 第四題：商品特賣問題

回應(0)