POJ 1328 Radar Installation贪心算法

题意
在一个平面直角坐标系上，有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个雷达，最终得到的雷达个数即为正解，即用最少的点去遍布所有的区间。无解的情况即为某岛屿的纵坐标大于雷达的半径，因此在读入数据时即可作出判断。

注意点
边界情况

#include <cstdio>
#include <cstdlib>
#include <math.h>
#include <vector>
#include <queue>
using namespace std;
const int N = 1010;
int xisland[N], yisland[N];

struct node{
    double left, right;
}node[N];

struct cmp{
    bool operator () (const int a, const int b) const{
        return node[a].left > node[b].left ? 1 : node[a].left == node[b].left ? node[a].right < node[b].right : 0;
}};

double range(int y, int rf){
    return sqrt(rf - pow((double)y, 2));
}

void work(int n, int d, int rf, int kase)
{
    int num = 0;
    double temp, l, r;
    priority_queue<int, vector<int>, cmp> pq;
    for(int i=0; i<n; ++i)
    {
        scanf("%d %d", xisland+i, yisland+i);
        if(yisland[i] > d)
        {
            for(++i; i<n; ++i)
                scanf("%d %d", xisland+i, yisland+i);
            printf("Case %d: -1\n", kase);
            return ;
        }
        temp = range(yisland[i], rf);
        node[i].left = (double)xisland[i] - temp;
        node[i].right = (double)xisland[i] + temp;
        pq.push(i);
        printf("%d %lf %lf\n", kase, node[i].left, node[i].right);
    }
    for(; !pq.empty(); ++num)
    {
        l = node[pq.top()].left;
        r = node[pq.top()].right;
        pq.pop();
        while(!pq.empty() && node[pq.top()].left <= r)
        {
            l = node[pq.top()].left > l ? node[pq.top()].left : l;
            r = node[pq.top()].right < r ? node[pq.top()].right : r;
            pq.pop();
        }
    }
    printf("Case %d: %d\n", kase, num);
}

int main(void)
{
    int n, d;
    for(int kase=0; scanf("%d %d", &n, &d), n||d; )
        work(n, d, d*d, ++kase);
    return 0;
}

测试数据

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