A810.Gold King大范围洒洒水

普及-

官方

通过率:0%

时间限制:1.00s

内存限制:128MB

题目描述

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

输入格式

第一行输入一个正整数 NN 表示共有 N(0<N<15)N(0<N<15) 次测试数据。 每一组测试数据的第一行有三个数 n,w,h,nn,w,h,n 表示共有 nn 个喷水装置,ww 表示草坪的横向长度,hh 表示草坪的纵向长度。

随后的 nn 行,都有两个整数 xi(0xi200)x_i(0\le x_i\le 200)ri(0<ri<100)r_i(0<r_i<100), xix_i表示第 ii 个喷水装置的的横坐标(最左边为00),rir_i 表示该喷水装置能覆盖的圆的半径。

输出格式

每组测试数据输出一个正整数,表示共需要多少个喷水装置,每个输出单独占一行。

如果不存在一种能够把整个草坪湿润的方案,请输出 00

输入输出样例

  • 输入#1

    2
    2 8 6
    1 1
    4 5
    2 10 6
    4 5
    6 5

    输出#1

    1
    2

说明/提示

10w15010\le w\le 150

2h1202\le h\le 120

0<Ri<150<Ri<15

0<n<=100000<n<=10000

0xi2000\le xi\le 200

0<ri<1000<ri<100

首页