Question

c++问题，求大师帮助。

长 L 米，宽 W 米的草坪里装有 n 个浇灌喷
头，每个喷头都装在草坪的中心线上（离两边各 w ÷ 2 米）。
我们知道每个喷头的位置（离草坪中心新左端的距离），
以及它能覆盖的浇灌距离。

请问：如果要同时浇灌整块草坪，最少需要打开多少个喷头。

输入格式

输入包含若干组测试数据。

第一行一个整数 T 表示测试数据组数。

每一组数据的第一行是整数 n, L,和W 的值，其中 n ≤ 10000。

接下来n行，每行包含两个整数，给出一个喷头的位置和浇灌半径。

输出格式

对于每组测试数据输出一个数字，表示要浇灌
整块草坪所需喷头数目的最小值，如果所有喷
头都打开还不能浇灌整块草坪，则输出 -1。

样例输入

3
8 20 2
5 3
4 1
1 2
7 2
10 2
13 3
16 2
19 4
3 10 1
3 5
9 3
6 1
3 10 1
5 3
1 1
9 1
样例输出

6
2
-1

Answer 1

哈哈哈这道题我做过，我曾经还向我们学校的OIer们讲过这道题。
此题是NOIp 2008的“喷水装置”。以下讲下思路--
看起来是个圆，其实它浇灌的有效范围是草坪与圆相交出的长方形。如下图：

因此可以过滤掉直径比长方形宽小的圆。这样处理后，就转化成了在长方形长上的线段覆盖问题。dp一下就可以了。
标程：
# include # include # include using namespace std; int cmp(double a, double b) { return a > b; } int main(void) { int n; scanf("%d", &n); while (n--) { int num; double in[601]; double allsum = 0.0; double dis = 0.0; int count = 0; int i; scanf("%d", &num); for (i = 0; i < num; i++) { scanf("%lf", &in[i]); } sort(in, in + num, cmp); i = 0; while (allsum - 20.0 < 0.000001) { dis = 2 * sqrt(in[i] * in[i] - 1); i++; count ++; allsum += dis; } printf("%d\n", count); } return 0; }

望采纳谢谢！我很努力的！