Toggle navigation
CSUOJ
F.A.Qs
ProblemSet
Source/Category
Status
Ranklist
Contest
Login
Language
中文
ئۇيغۇرچە
English
فارسی
ไทย
한국어
Problem1479--喷水装置
1479: 喷水装置
[Creator :
]
Time Limit :
1.000
sec
Memory Limit :
512 MB
Solved: 0
Submit: 1
Statistics
Description
长
LL
L
米,宽
WW
W
米的草坪里装有
nn
n
个浇灌喷头。每个喷头都装在草坪中心线上(离两边各
W2\frac{W}{2}
2
W
米)。我们知道每个喷头的位置(离草坪中心线左端的距离),以及它能覆盖到的浇灌范围。
请问:如果要同时浇灌整块草坪,最少需要打开多少个喷头?
Input
输入包含若干组测试数据。
第一行一个整数
TT
T
表示数据组数;
每组数据的第一行是整数
nn
n
、
LL
L
和
WW
W
;
接下来的
nn
n
行,每行包含两个整数,给出一个喷头的位置和浇灌半径(上面的示意图是样例输入第一组数据所描述的情况)。
Output
对每组测试数据输出一个数字,表示要浇灌整块草坪所需喷头数目的最小值。如果所有喷头都打开也不能浇灌整块草坪,则输出
−1-1
−
1
。
Sample Input
Copy
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
Sample Output
Copy
6 2 -1
HINT
对于
100%100\%
1
0
0
%
的数据,
n≤15000n \le 15000
n
≤
1
5
0
0
0
Source/Category