解题思路

1. 主函数 main：
   • 使用 while 循环读取输入的海岛数量 island 和雷达覆盖半径 radius，当 island 和 radius 都为 0 时结束循环。
   • 为每个海岛创建一个 Interval 结构体来表示其在 x 轴上的投影区间。
   • 读取每个海岛的坐标 x 和 y，如果 y 大于 radius，则该海岛不在雷达覆盖范围内，标记 isSolvable 为 false。
   • 根据勾股定理计算海岛在 x 轴上投影区间的左端点 left 和右端点 right。
   • 调用 solve 函数计算覆盖所有海岛所需的最少雷达数量 minRadar，如果 isSolvable 为 false，则 minRadar 为 -1。
   • 输出每个测试用例的结果，格式为 "Case X: Y"，其中 X 为测试用例编号，Y 为最少雷达数量。
   • 释放 intervals 数组的内存。
2. 函数 solve：
   • 使用 sort 函数对 intervals 数组按照区间左端点进行排序，排序规则由 compare 函数确定。
   • 初始化最少雷达数量 minPoint 为 1，并将第一个区间的右端点赋值给 right。
   • 遍历 intervals 数组：
     • 如果当前区间的左端点大于 right，则需要新增一个雷达，minPoint 加 1，并将当前区间的右端点赋值给 right。
     • 如果当前区间的右端点小于 right，则更新 right 为当前区间的右端点。
   • 返回最少雷达数量 minPoint。
3. 函数 compare：
   • 比较两个区间 a 和 b 的左端点，返回 a 的左端点小于等于 b 的左端点的结果。

#include <math.h>
#include <algorithm>
#include <iostream>
using namespace std;


// 海岛在x轴上的投影区间
struct Interval {
    double left;    // 左端点在x轴上的坐标
    double right;    // 右端点在x轴上的坐标
};

int solve(Interval* intervals, int size);

bool compare(Interval a, Interval b);


int main(void) {
    int island, radius, testCase = 0;
    while ((cin >> island >> radius) && island && radius) {
        const double R2 = radius * radius;    // 半径平方
        Interval* intervals = new Interval[island];

        bool isSolvable = true;
        for (int i = 0; i < island; i++) {
            double x, y;
            cin >> x >> y;
            if (y > radius) {    // 存在海岛不在雷达的最大影响范围，无解
                isSolvable = false;
            }

            double offset = sqrt(R2 - y * y);    // 勾股定理
            intervals[i].left = x - offset;
            intervals[i].right = x + offset;
        }

        int minRadar = (isSolvable ? solve(intervals, island) : -1);
        cout << "Case " << ++testCase << ": " << minRadar << endl;
        delete[] intervals;
    }
    return 0;
}


int solve(Interval* intervals, int size) {
    sort(intervals, intervals + size, compare);

    int minPoint = 1;
    double right = intervals[0].right;
    for (int i = 1; i < size; i++) {

        // 区间i-1 与 区间i 无交集
        if (intervals[i].left > right) {
            minPoint++;
            right = intervals[i].right;

            // 区间i-1 在 区间i 内部
        }
        else if (intervals[i].right < right) {
            right = intervals[i].right;

        }
        else {
            // Undo: 区间i-1 与 区间i 相交 
        }
    }
    return minPoint;
}


bool compare(Interval a, Interval b) {
    return a.left <= b.left;
}