2437: LazyLie的草坪
内存限制:128 MB
时间限制:1.000 S
评测方式:文本比较
命题人:
提交:35
解决:6
题目描述
LazyLie有个长L米、宽W米的草坪,草坪里装有n个浇灌喷头。每个喷头都装在草坪的中心线上(即距离草坪上下两端各W/2米),喷头浇灌的范围是是一个圆。我们知道每个喷头的位置(距离草坪最左端的距离),以及每个喷头所能浇灌的半径。
LazyLie想知道,如果要同时浇灌整块草坪,最少需要打开多少个
输入
第一行,三个整数n、L和W;
之后n行,每行两个整数X,R,表示位置和半径。
输出
输出一行一个数字,表示要浇灌整块草坪所需喷头数目的最小值。如果所有喷头都打开也不能浇灌整块草坪,则输出-1。
样例输入 复制
9 20 2
2 1
1 2
6 2
5 3
9 2
12 3
16 2
17 1
19 4
样例输出 复制
6
提示
【输入样例2】
3 10 1
5 3
1 1
9 1
【输出样例2】
-1
对于20%的数据 n<=25
对于50%的数据 n<=5000
对于100%的数据 n<=1000000,w<=l<=2^31-1