A271 | $Gold King大范围洒洒水$

时间限制1s

内存限制128MB

通过 / 提交0/0

题目描述

经历过干旱洗礼的青青草原，学会了节约化生产生活，摒弃之前豪放型生活资料生产。决定在青青草原推广$Gold King$ 式喷水浇灌农场项目。 根据青青草原不同农场大小，都要适应，例如：横向长为实数$w(10\le w\le 150)$，纵向长为实数 $h (2\le h\le 120)$，在它的橫向中心线上不同位置处装有 $n(0<n\le 10000)$个点状的喷水装置，每个喷水装置i喷水的效果是让以它为中心半径为 $Ri(0<Ri<15)$ 的圆都被润湿。请在给出的喷水装置中选择尽量少的喷水装置，把整个草坪全部润湿。 ![](/uploads/acgo/image/bf63f4d2a974408b_9e140b33eab8.png)

第一行输入一个正整数 $N$ 表示共有 $N(0<N<15)$ 次测试数据。 每一组测试数据的第一行有三个数 $n,w,h,n$ 表示共有 $n$ 个喷水装置，$w$ 表示草坪的横向长度，$h$ 表示草坪的纵向长度。 随后的 $n$ 行，都有两个整数 $x_i(0\le x_i\le 200)$ 和 $r_i(0<r_i<100)$, $x_i$表示第 $i$ 个喷水装置的的横坐标（最左边为$0$），$r_i$ 表示该喷水装置能覆盖的圆的半径。

每组测试数据输出一个正整数，表示共需要多少个喷水装置，每个输出单独占一行。 如果不存在一种能够把整个草坪湿润的方案，请输出 $0$ 。

输入 #1

输出 #1

1
2

C++ 编辑器

输入

输出