UVA10382 UVA10382 Watering Grass

题目描述

![题目描述图片](https://cdn.luogu.com.cn/upload/vjudge_pic/UVA10382/388518f8e3e8ce10ab22098197e19c4149d773e6.png) 长 $L$ 米,宽 $W$ 米的草坪里装有 $n$ 个浇灌喷头。每个喷头都装在草坪中心线上(离两边各 $\frac{W}{2}$ 米)。我们已经知道每个喷头的位置(离草坪中心线最左端的距离),以及它能覆盖到的浇灌范围。 求这些喷头能否完整浇灌整块草坪,如果能,那么完成浇灌最少需要打开多少个喷头?

输入格式

![输入格式图片](https://cdn.luogu.com.cn/upload/vjudge_pic/UVA10382/043b45f29e67e742e9130267198ea7bfe60d35bf.png) 给定若干组测试数据。 每组数据的第一行是整数 $n$、$L$ 和 $W$; 接下来的 $n$ 行,每行包含两个整数,一个喷头的位置和它的浇灌半径(例题中的示意图所描述的情况是输入样例的第一组数据)。

输出格式

![输出格式图片](https://cdn.luogu.com.cn/upload/vjudge_pic/UVA10382/73a7083285137761e2b9ea258ed541ab44ff938d.png) 每组测试数据输出一个数字,表示要浇灌整块草坪所需的最少喷头数。如果打开所有喷头都不能完整浇灌草坪,则输出 $-1$。

说明/提示

#### 数据规模与约定 对于全部的测试点,保证 $n,l,w \le {10}^4$。