题意简述

如图所示，x轴上方有n（1≤n≤1000）个岛屿（坐标均为整数）， 在x轴上可以放置覆盖半径为d（整数）的雷达。问最少放置多少个雷达能够覆盖所有岛屿？如果无法全部覆盖则输出-1。

算法分析

这道题折磨了我好几天，一直WA一直WA…本来觉得没多难都被WA崩溃了…好了不扯了进正题。

首先分析无解的情况。容易得到：当且仅当某一岛屿的纵坐标大于雷达半径时，此组数据无解。 这个可以在读入时直接判断。需要注意的是，即便已经得到无解结论，也应等所有数据输入完毕再输出-1。

接下来就是求解过程了。

这题用贪心。但刚拿到手时，由于思考的局限性给出了错误的贪心策略。导致WA了好几次…（血泪史啊！T.T）下面先说错误的：

• 错误贪心策略：

1. 所有岛屿按照横坐标从小到大排序。若横坐标相等则按纵坐标从大到小排序。
2. 首先利用第一个岛屿坐标，选择能够覆盖住它的，在它右侧距离最远的x轴上的点，放下第一个雷达。（位置可由勾股确定）。如图所示：橘色为雷达位置。
3. 扫描下一个点，如果在当前雷达覆盖范围内则继续向后扫描，否则以该点坐标为基准，依照步骤2中方法确立一个新雷达位置。直到所有岛屿被覆盖。

这个贪心策略至少我当时完全没有想到任何破绽…可是一直WA一直WA…直到学长给了这样一组数据：

其中雷达半径为5。这组数据只需在（1,0）放置一个雷达即可。但按照上面的策略，则需放置两个雷达。分别在（1,0）和（3,0）。

这让我相当郁闷……最后无奈上网找了其他人的AC程序，才找到正确的贪心策略。

• 正确贪心策略：

1. 首先在读入时，用勾股算出x轴上能够覆盖住当前点的区间。
2. 将区间按照左端点排序。
3. 因为若两区间有包含关系，则小区间内存在雷达即可满足大区间需求。所以从右向左扫描所有区间，标记因包含关系无需处理的大区间。
4. 从左向右扫描。首先判断该区间是否被标记。若区间需要处理，则判断当前雷达是否在区间内。若在则继续向下扫描。若不在，则选取区间右端点标记为新雷达位置。同时累加器自增。扫描结束后输出累加器值即可。

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;
}