P1325 雷达安装
题目
假设海岸线是一条无限延伸的直线。它的一侧是陆地，另一侧是海洋。每一座小岛是在海面上的一个点。雷达必须安装在陆地上（包括海岸线），并且每个雷达都有相同的扫描范围 \(d\)。你的任务是建立尽量少的雷达站，使所有小岛都在扫描范围之内。
数据使用笛卡尔坐标系，定义海岸线为 \(x\) 轴。在 \(x\) 轴上方为海洋，下方为陆地。
输入
第一行包括 \(2\) 个整数 \(n\) 和 \(d\)，\(n\) 是岛屿数目，\(d\) 是雷达扫描范围。
接下来 \(n\) 行，每行两个整数，为岛屿坐标。
输出
一个整数表示最少需要的雷达数目，若不可能覆盖所有岛屿，输出 -1。
样例
输入
3 2
1 2
-3 1
2 1
输出
2
提示
样例 1 解释
数据范围
对于全部数据，\(n\le1000\)，$ d \le 2\times 10^4\(，\) | x_i | \le 2 \times 10^6 \(，\) 0 \le y_i \le 2\times 10^4$。
思路
在解决本题之前，先分析一下区间选点问题：
数轴上有 \(n\) 个闭区间 \(\lbrack a_i,b_i \rbrack\)。取尽量少的点，使得每个区间内都至少有一个点（不同区间内含的点可以是同一个）。
- 比较容易想到：如果有一大一小区间，由于小区间被满足时大区间一定也被满足，所以在区间包含的情况下，大区间不需要考虑。（如上图。）
-
上述两种情况同时可以引发思考，如何对区间进行排序？假设按照区间右端点进行排序。如上图，则应该选择区间 \(1\) 的右端点 \(b_1\) 作为基准值（尽量更右），一旦区间 \(2\) 的左端点 \(a_2\) 大于 \(b_1\) 时，则说明增加一个点覆盖 \(b_2\)，且更新基准值为 \(b_2\) 供后面的区间进行比较。如果区间 \(2\) 的左端点 \(a_2\) 小于等于 \(b_1\)，则不需要增加新的点覆盖，基准值依然为 \(b_1\)。
-
当进行右端点排序时，如果右端点相同，那么该如何选点？为保持相同的规律，依然选择上一个区间的右端点，左端点可任意排序。
接下来回归本题，通过分析发现该题目本质上是一个区间点覆盖问题，采用贪心策略，题目中说雷达必须安装到陆地上（包括海岸线），可以很容易地想到，对于每个不在海岸线上的雷达 \(A\)，和它的横坐标相同的海岸线上的雷达 \(B\) 的海面探测范围一定包含 \(A\) 的探测范围，因此，雷达一定要建在海岸线上。题目要求每个岛屿都要覆盖到，雷达的探测距离为 \(d\)，一个雷达想要探测到它，必须和它的距离小于等于 \(d\)。
由勾股定理 \(d^2=s^2+y^2\) 推出探测到一个岛屿 \(I(x,y)\) 的海岸线区间为 \(\lbrack x-\sqrt{d^2-y^2},x+\sqrt{d^2-y^2}\rbrack\)，这样每个岛屿都对应一个区间。我们需要在 \(x\) 轴上取尽量少的点，使每个区间上都至少有一个点，于是问题转换为区间点覆盖问题。按照区间右端点升序排序，如果右端点相同，按照区间左端点升序排序或降序排序。记录第一个区间右端点 \(nx\)，枚举之后的区间，若区间左端点小于 \(nx\)，继续枚举，否则答案累加 \(1\)，且更新 \(nx\) 为当前区间右端点。
代码
#include <bits/stdc++.h>
using namespace std;
const int N = 1000006;
int n, ans = 1, nx;
double d;
struct Range
{
double a, b;
Range()
{
}
Range(double x, double y)
{
a = x;
b = y;
}
} r[N];
bool cmp(Range x, Range y)
{
if (x.b < y.b)
return 1;
else if (x.b == y.b && x.a > y.a)
return 1;
return 0;
}
int main()
{
scanf("%d %lf", &n, &d);
double a, b;
for (int i = 1; i <= n; i ++ )
{
scanf("%lf %lf", &a, &b);
if (b <= d)
r[i] = Range(a - sqrt(d * d - b * b), a + sqrt(d * d - b * b));
// 转换成区间问题
else
{
printf("-1");
return 0;
}
}
sort(r + 1, r + 1 + n, cmp);
nx = r[1].b;
for (int i = 2; i <= n; i ++ )
{
if (r[i].a > nx)
{
ans ++;
nx = r[i].b;
}
}
printf("%d", ans);
return 0;
}