2012-09-16 12:14:06Morris
[ZJ][sort] a480. 導彈攔截系統
內容 ：
某個國家研發了一套導彈攔截系統，只要設定了防護半徑 r，在距離系統設置處 r 以內的範圍都會受到防護。此外，他們發現，啟用該系統會消耗大量的能源，且能源消耗為 r2。
在研發完成之際，敵國隨即向他們發射飛彈展開攻擊。不幸的是，該系統仍在試驗階段，所以目前僅設置於兩處 (x1, y1) 與 (x2, y2)。由於能源消耗過於龐大，要使防護持久就必須讓能源消耗越小越好。因此，他們希望能以最少的能源消耗下防護境內所有的 n 個城市。
為了簡單起見，城市位置以一點 (xi, yi) 來表示。
輸入說明
：
第一行有兩個整數 x1, y1，代表第一座導彈攔截系統的座標位置。
第二行也有兩個整數 x2, y2，代表第二座導彈攔截系統的座標位置。
第三行有一個正整數 n，其中 n ≦ 1,000,000，代表這個國家的城市個數。
接下來的 n 行，每行有兩的整數 xi, yi，代表輸入的第 i 個城市的座標位置。
輸入的座標 (x, y) 皆滿足 |x| ≦ 10,000 且 |y| ≦ 10,000。
輸出說明
：
請輸出一個正整數 p，代表達成城市防護的能源消耗最小值。
範例輸入 ：
0 0 0 2 4 0 3 1 -1 1 0 1 1
範例輸出 ：
3
提示
：
將第一座導彈攔截系統的 r 設為 √(2)，第二座導彈攔截系統的 r 設為 1，即可得到能源消耗最小值 3。
出處
：
100 彰雲嘉區學科能力競賽資訊科
(管理：xavier13540)
#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;
}
對第一位置的距離, 對第二位置的距離 ->(a, b)
先為 a 做升排序
之後窮舉 p = D[i].a + max(D[i+k].b) 1 <= k
ANSI C 的排序比較慢, 所以貼 C++ 的
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;
}