题意
在一个平面直角坐标系上，有n个给出坐标的岛屿，问在X轴上至少需要放置多少个半径为d的雷达可以遍布所有岛屿？（若无法遍布所有岛屿则输出-1）
样例输入
3 2
1 2
-3 1
2 1
1 2
0 2
0 0
样例输出
Case 1: 2
Case 2: 1
思路
先求出各个岛屿能被搜索到的放置雷达区间，排序（也可用优先队列），然后把存在重叠部分的区间算作1个雷达，最终得到的雷达个数即为正解，即用最少的点去遍布所有的区间。无解的情况即为某岛屿的纵坐标大于雷达的半径，因此在读入数据时即可作出判断。
注意点
边界情况
1 #include <cstdio> 2 #include <cstdlib> 3 #include <math.h> 4 #include <vector> 5 #include <queue> 6 using namespace std; 7 const int N = 1010; 8 int xisland[N], yisland[N]; 9 10 struct node{ 11 double left, right; 12 }node[N]; 13 14 struct cmp{ 15 bool operator () (const int a, const int b) const{ 16 return node[a].left > node[b].left ? 1 : node[a].left == node[b].left ? node[a].right < node[b].right : 0; 17 }}; 18 19 double range(int y, int rf){ 20 return sqrt(rf - pow((double)y, 2)); 21 } 22 23 void work(int n, int d, int rf, int kase) 24 { 25 int num = 0; 26 double temp, l, r; 27 priority_queue<int, vector<int>, cmp> pq; 28 for(int i=0; i<n; ++i) 29 { 30 scanf("%d %d", xisland+i, yisland+i); 31 if(yisland[i] > d) 32 { 33 for(++i; i<n; ++i) 34 scanf("%d %d", xisland+i, yisland+i); 35 printf("Case %d: -1 ", kase); 36 return ; 37 } 38 temp = range(yisland[i], rf); 39 node[i].left = (double)xisland[i] - temp; 40 node[i].right = (double)xisland[i] + temp; 41 pq.push(i); 42 printf("%d %lf %lf ", kase, node[i].left, node[i].right); 43 } 44 for(; !pq.empty(); ++num) 45 { 46 l = node[pq.top()].left; 47 r = node[pq.top()].right; 48 pq.pop(); 49 while(!pq.empty() && node[pq.top()].left <= r) 50 { 51 l = node[pq.top()].left > l ? node[pq.top()].left : l; 52 r = node[pq.top()].right < r ? node[pq.top()].right : r; 53 pq.pop(); 54 } 55 } 56 printf("Case %d: %d ", kase, num); 57 } 58 59 int main(void) 60 { 61 int n, d; 62 for(int kase=0; scanf("%d %d", &n, &d), n||d; ) 63 work(n, d, d*d, ++kase); 64 return 0; 65 }
测试数据
3 2 1 2 -3 1 2 1 1 2 0 2 2 5 -3 4 -6 3 4 5 -5 3 -3 5 2 3 3 3 20 8 -20 7 -18 6 -5 8 -21 8 -15 7 -17 5 -1 5 -2 3 -9 6 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 7 9 6 10 5 0 0 2 3 0 2 2 3 2 3 0 2 1 3 3 3 1 2 -3 2 2 4 8 5 2 4 -4 4 -3 3 -3 1 -3 0 -1 0 0 5 6 0 3 0 1 2 -3 1 2 1 3 2 1 2 -3 1 2 1 1 2 0 2 2 3 0 2 2 3 4 -5 4 3 4 3 2 3 6 -9 3 -3 1 2 -3 2 2 1 6 2 1 2 1 2 1 2 -3 1 2 1 0 0 1 2 0 2 2 3 0 2 1 3 3 10 1 10 2 3 4 5 3 5 1 10 2 3 4 5 4 7 1 10 2 3 4 5 0 0 3 9 1 10 2 3 4 5 0 0
Case 1: 2 Case 2: 1 Case 3: 1 Case 4: 2 Case 5: 4 Case 6: 1 Case 7: 1 Case 8: -1 Case 9: 3 Case 10: -1 Case 11: 2 Case 12: 1 Case 13: 1 Case 14: -1 Case 15: -1 Case 16: 2 Case 17: 1 Case 18: 1 Case 19: 1 Case 20: -1 Case 21: -1 Case 22: -1