题意简述
如图所示，x轴上方有n（1≤n≤1000）个岛屿（坐标均为整数）， 在x轴上可以放置覆盖半径为d（整数）的雷达。问最少放置多少个雷达能够覆盖所有岛屿？如果无法全部覆盖则输出-1。
算法分析
这道题折磨了我好几天，一直WA一直WA…本来觉得没多难都被WA崩溃了…好了不扯了进正题。
首先分析无解的情况。容易得到：当且仅当某一岛屿的纵坐标大于雷达半径时，此组数据无解。 这个可以在读入时直接判断。需要注意的是，即便已经得到无解结论，也应等所有数据输入完毕再输出-1。
接下来就是求解过程了。
这题用贪心。但刚拿到手时，由于思考的局限性给出了错误的贪心策略。导致WA了好几次…（血泪史啊！T.T）下面先说错误的：
- 错误贪心策略：
- 所有岛屿按照横坐标从小到大排序。若横坐标相等则按纵坐标从大到小排序。
- 首先利用第一个岛屿坐标，选择能够覆盖住它的，在它右侧距离最远的x轴上的点，放下第一个雷达。（位置可由勾股确定）。如图所示：
橘色为雷达位置。 - 扫描下一个点，如果在当前雷达覆盖范围内则继续向后扫描，否则以该点坐标为基准，依照步骤2中方法确立一个新雷达位置。直到所有岛屿被覆盖。
这个贪心策略至少我当时完全没有想到任何破绽…可是一直WA一直WA…直到学长给了这样一组数据：
其中雷达半径为5。这组数据只需在（1,0）放置一个雷达即可。但按照上面的策略，则需放置两个雷达。分别在（1,0）和（3,0）。
这让我相当郁闷……最后无奈上网找了其他人的AC程序，才找到正确的贪心策略。
正确贪心策略：
- 首先在读入时，用勾股算出x轴上能够覆盖住当前点的区间。
- 将区间按照左端点排序。
- 因为若两区间有包含关系，则小区间内存在雷达即可满足大区间需求。所以从右向左扫描所有区间，标记因包含关系无需处理的大区间。
- 从左向右扫描。首先判断该区间是否被标记。若区间需要处理，则判断当前雷达是否在区间内。若在则继续向下扫描。若不在，则选取区间右端点标记为新雷达位置。同时累加器自增。扫描结束后输出累加器值即可。
Problem Status: AC。时间0ms，内存392k
——————————————————————分割线——————————————————————
TIPS:
在思考这个正确的贪心策略时，发现网上的那个AC程序是这样实现去除包含关系的：
for (i = 0; i < n; i++)
if (b[i] == 0)
if (pos < area[i][0]) {
ans++;
pos = area[i][1];
}b[i]是标记数组，pos表示当前雷达位置。area[i]是存储区间的数组。其中[0]存左端点，[1]存右端点。
这种方法其实有一个漏洞：无法去除两个左端点相同的区间的包含关系。例如：区间[1,2]和[1,3]无论其先后顺序，都不会被标记为存在包含的区间。
但如果继续考虑下面判断是否新建雷达的算法，则可以容易发现这个并不妨碍统计雷达个数。
可参照下面的程序样例进行理解。
——————————————————————分割线——————————————————————
为进行比对，下面将贴出错误贪心策略的代码及正确贪心策略的代码。
程序样例
错误贪心策略：
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
int comp(const void * a, const void * b) {
int *c, *d;
c = (int *) a;
d = (int *) b;
if ( *c > *d) return 1;
if ( *c < *d) return -1;
c++;
d++;
if (( *c) < ( *d)) return 1;
return -1;
}
double dis(double pos, int x, int y) {
double a, b, c;
a = y * y;
b = (x - pos) * (x - pos);
return sqrt(a + b);
}
int main() {
int n, d, i, p[1000][2], ans = 1, c = 0, b[1000] = {
1
};
double pos;
scanf("%d%d", &n, &d);
while (!(n == 0 && d == 0)) {
c++;
if (n == 0) {
printf("Case %d: 0\n", c);
scanf("%d%d", &n, &d);
continue;
}
ans = 1;
for (i = 0; i < n; i++) {
scanf("%d%d", &p[i][0], &p[i][1]);
if (p[i][2] > d) ans = -1;
}
if (ans == -1 || d == 0) {
printf("Case %d: -1\n", c);
scanf("%d%d", &n, &d);
continue;
}
comp(p[0], p[1]);
qsort(p, n, 2 * sizeof(int), comp);
pos = p[0][0] + sqrt(d * d - p[0][1] * p[0][1]);
for (i = 1; i < n; i++)
if (dis(pos, p[i][0], p[i][1]) <= d * 1.0)
continue;
else {
ans++;
pos = p[i][0] + sqrt(d * d - p[i][1] * p[i][1]);
}
printf("Case %d: %d\n", c, ans);
scanf("%d%d", &n, &d);
}
return 0;
}正确贪心策略：
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
int comp(const void * a, const void * b) {
double * c, * d;
c = (double * ) a;
d = (double * ) b;
if ( * c > * d) return 1;
return -1;
}
int main() {
int n, d, c = 0, p[1000][2], i, ans, b[1000] = {0};
double pos, area[1000][2], t;
scanf("%d%d", & n, & d);
while (!(n == 0 && d == 0)) {
c++;
ans = 0;
for (i = 0; i < n; i++) {
scanf("%d%d", & p[i][0], & p[i][1]);
if (p[i][1] > d) ans = -1;
else {
area[i][0] = sqrt(d * d - p[i][1] * p[i][1]);
area[i][1] = p[i][0] + area[i][0];
area[i][0] = p[i][0] - area[i][0];
}
b[i] = 0;
}
if (ans == -1 || d == 0) {
printf("Case %d: -1\n", c);
scanf("%d%d", & n, & d);
continue;
}
qsort(area, n, 2 * sizeof(double), comp);
t = area[n - 1][1];
for (i = n - 2; i >= 0; i--)
if (area[i][1] >= t) b[i] = 1;
else t = area[i][1];
pos = -2100000000;
for (i = 0; i < n; i++)
if (b[i] == 0)
if (pos < area[i][0]) {
ans++;
pos = area[i][1];
}
printf("Case %d: %d\n", c, ans);
scanf("%d%d", & n, & d);
}
return 0;
}