算法题（156）：雷达探测

审题：
本题需要我们完成多组情况的雷达选取，目的是让雷达数最小且能覆盖所有岛屿，最终输出的结果是雷达个数

思路：
方法一:贪心+降维

本题的题目背景是二维的，我们直接对二维的题目进行思考根本没有思路，而因为雷达只能放在海岸线上，这是一维的放置方式，所以我们尝试降维思考。

由于雷达的极限探测半径是d，所以我们可以根据极限探测半径把雷达极限放置距离测算出来，通过勾股定理可知：，所以left = x-l,right = x+l。岛屿坐标设为(x,y)

而岛屿的雷达放置区间如果有重叠就说明可以把雷达放在区间内从而同时覆盖两座岛屿，我们找出区间重叠的总个数就可以得到最小的雷达个数需求

而我们对于区间问题第一步都是先确定排序方式：我们先尝试左端点升序

左端点升序排完后，能重叠的区间都是连续排列的，我们先以a[1].r作为第一个基准点，遇到新区间的left小于等于r，说明有重叠，此时让r = min(r,right)，因为我们要保留的是右端点更小的区间，这样才能让所有区间都有重叠。若left大于r，没重叠，说明要放新的雷达，answer++，然后r = right。

左端点升序逻辑完善，可以使用。

解题：
 

#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
const int N = 1010;
int n;
double d;
struct space
{double l;double r;
}a[N];
bool cmp(space& s1, space& s2)
{return s1.l < s2.l;
}
int main()
{double cnt = 0;while (cin >> n >> d , n && d){cnt++;bool flag = false;for (int i = 1; i <= n; i++){double x = 0, y = 0;cin >> x >> y;//特殊处理if (y > d) flag = true;//降维double l = sqrt(d * d - y * y);a[i].l = x - 1;a[i].r = x + l;}sort(a + 1, a + 1 + n, cmp);//左端点升序排序cout << "Case " << cnt << ": ";if (flag) cout << -1 << endl;else//区间筛选{double answer = 1;double r = a[1].r;for (int i = 2; i <= n; i++){double left = a[i].l;double right = a[i].r;if (left <= r)//重叠{r = min(r, right);}else{answer++;r = right;}}cout << answer << endl;}}return 0;
}

1.数据录入的while逻辑：

由于涉及多组数据录入且录入终止条件为n,d都为0，所以我们的while语句中使用了逗号表达式，先执行数据录入，然后判断n,d是否都为0，都为0就退出循环

2.特殊处理：由于y可能会大于d，此时雷达永远无法探测到该岛屿，我们需要输出-1，所以用一个flag来标记是否出现这种情况

UVA1193 Radar Installation - 洛谷