题库 信息学奥赛题库 题目列表 信息学奥赛练习题:【例题3】喷水装置【题目描述】长&...
问答题

信息学奥赛练习题:【例题3】喷水装置

【题目描述】

长 L米,宽 W米的草坪里装有 n个浇灌喷头。每个喷头都装在草坪中心线上(离两边各 W/2米)。我们知道每个喷头的位置(离草坪中心线左端的距离),以及它能覆盖到的浇灌范围。

 

请问:如果要同时浇灌整块草坪,最少需要打开多少个喷头?

 

【输入】

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

 

第一行一个整数 T表示数据组数;

 

每组数据的第一行是整数 n、L和 W;

 

接下来的 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

【提示】

数据范围:

对于 100% 的数据,n≤15000。

题目信息
完善程序 2023年 练习
-
正确率
0
评论
127
点击