算法
(贪心) $O(nlogn)$
如下图所示，对于任意一个小岛 $(x, y)$，我们都可以在海岸线上求出能覆盖该小岛的建造雷达的区间 $[a, b]$。
由勾股定理可知：
- $a = x - \sqrt{d^2 - y^2}$;
- $b = x + \sqrt{d^2 - y^2}$;
将所有小岛转化成区间后，问题转化为：给定 $n$ 个区间，在 $x$ 轴上选择尽量少的点，使得所有区间至少包含一个点。
我们先给出做法，再证明其正确性。
算法步骤：
- 将所有区间按右端点从小到大排序；
- 依次考虑每个区间：
- 如果当前区间包含最后一个选择的点，则直接跳过；
- 如果当前区间不包含最后一个选择的点，则在当前区间的右端点的位置选一个新的点；
证明：
首先上述做法一定可以保证所有区间都至少包含一个点。
然后我们再证明这样选出的点的数量是最少的，不妨设选出的点数是 $m$：
- 按照上述做法，我们选择的点都是某个区间的右端点，而且由于区间按右端点排好序了，所以我们选择的点也是排好序的；
- 只有在当前区间和上一个点所对应的区间是没有交集时，我们才会选择一个新点，所以所有选出的点所对应的区间是如下图所示的情况，两两之间没有交集。
所以我们找到了 $m$ 个两两之间没有交集的区间，因此我们至少需要选 $m$ 个点。而且通过上述做法，我们可以只选 $m$ 个点。因此最优解就是 $m$。
时间复杂度
- 计算每个坐标所对应的区间，需要 $O(n)$ 的计算量；
- 将所有区间排序需要 $O(nlogn)$ 的计算量；
- 扫描所有区间需要 $O(n)$ 的计算量；
所以总共的时间复杂度是 $O(nlogn)$。
C++ 代码
#include <cstring>
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
typedef pair<double, double> PDD;
const int N = 1010;
const double eps = 1e-6, INF = 1e10;
int n, d;
PDD seg[N];
int main()
{
cin >> n >> d;
bool success = true;
for (int i = 0; i < n; i ++ )
{
int x, y;
cin >> x >> y;
if (y > d)
{
success = false;
break;
}
auto len = sqrt(d * d - y * y);
seg[i] = {x + len, x - len};
}
if (!success) puts("-1");
else
{
sort(seg, seg + n);
int res = 0;
double last = -INF;
for (int i = 0; i < n; i ++ )
{
if (seg[i].second > last + eps)
{
res ++ ;
last = seg[i].first;
}
}
cout << res << endl;
}
return 0;
}
有一说一 这里y总的证明和思路都 > 蓝书
我也是博采众家之长hh
y总，为啥不能是按左端点排序啊
y总这个pair是按照终点排序，如果用左端点排序是要重写小于号，我刚转明白
两种排序方法只会导致一种情况不同：假如a是-2到2，b是-1到1，按右端点排序先看b
再看a，此时last在1，也就是插在1的位置，1也是在a的区间内；而按左端点是先看a，到判断b时直接跳过去了，但此时last是插在2，也就是a的右端点，此时雷达已经超出了b的范围。所以右端点从小到大是确保当前插下的雷达一定在所有区间内。
y总 可以出书了。
雀食
直接sort不是按左端点排序吗？
pair的第一关键字存的是右端点。
究竟需不需要加eps处理呢
这题加不加都可以。
为啥不能直接贪心当前点的最右端，然后跳到下一个尚未被覆盖的点啊
做法不唯一，但每个做法最好想办法证明其正确性。
这题根据左端点和右端点排序分别会造成什么效果呢
根据右端点排序根据上述的证明可以保证选出的点数是最少的。根据左端点排序就要看后续的操作是啥了。
额 进阶指南上确实取了个min
左右是对称的，如果按左端点排序，后续的操作也对称一下就好了
因为你按照左断点再这么做的话，都无法保证每个区间里至少有一个点。如果你非要按照左端点排序，那么至少要从右边开始向左判断左端点。将第一个左端点当作区间最后一个点，往左遍历，如果当前区间不包含这个点，ret++，并且将这个新区见的左端点作为新的最后一个点。
确实。我开始按照左端点排序从左向右遍历时答案偏小。应该从右边开始向左遍历
图画的很好理解，感谢！
从左往右时，last要取个min
左端点排序没有问题！你这出错是因为你没有考虑每遍历一个区间就要维护一次最小值！
为啥不能按x排序 用倍增的思想取出一段区间 check判断这段区间x【mid】是否满足d范围条件 满足就倍增 不满足就回退
“覆盖所有区间的最少点数”
请问为什么不可以算：直线距离<= 2 * r那么贪啊，或者是按x与x +1的距离，我觉得这样非常有道理啊
而且如果最大以2R贪，他的长度还更大了。本来就必须在海岸线上，那就是把一个圆分成两半，就是2R啊
想问下pair第二关键字怎么直接排序呀，我是把区间的左右互换了😂
就是这样
写个bool cmp() return a.y < b.y
最后一个选择的点....原来是上一个选择的点 看了代码才知道
请问比较函数为什么不可以是“先比较L端点，从小到大排序，如果相等比较右端点，右端点大的在前面”。我觉得可以啊
这个证明可以
就很严谨。
这道题如果按照左端点排序 然后倒序遍历 如果当前区间与前面的区间有交集就为一个监控 如果没有交集就新建监控
上面这种策略好像会wa掉两个点 是为什么呢
这种做法和上述做法是对称的，算法本身应该没问题，可能是代码写错了。
对的 确实是我当时代码写错了 谢谢老师！
好滴，客气啦