Problem 1960 --喷水装置(二)

1960: 喷水装置(二)

"
Time Limit $1$ 秒/Second(s) Memory Limit $512$ 兆字节/Megabyte(s)
提交总数 $90$ 正确数量 $76$
裁判形式 标准裁判/Standard Judge 我的状态 尚未尝试
难度 分类标签 贪心 几何 排序
有一块草坪,横向长w,纵向长为h,在它的橫向中心线上不同位置处装有n(n<=10000)个点状的喷水装置,每个喷水装置i喷水的效果是让以它为中心半径为Ri的圆都被润湿。请在给出的喷水装置中选择尽量少的喷水装置,把整个草坪全部润湿。
第一行输入一个正整数N表示共有n次测试数据。
每一组测试数据的第一行有三个整数n,w,h,n表示共有n个喷水装置,w表示草坪的横向长度,h表示草坪的纵向长度。
随后的n行,都有两个整数xi和ri,xi表示第i个喷水装置的的横坐标(最左边为0),ri表示该喷水装置能覆盖的圆的半径。
每组测试数据输出一个正整数,表示共需要多少个喷水装置,每个输出单独占一行。
如果不存在一种能够把整个草坪湿润的方案,请输出0。
2
2 8 6
1 1
4 5
2 10 6
4 5
6 5
1
2

推荐代码 查看1960 所有题解 上传题解视频得图灵币

本题记录 用 户(点击查看用户) 运行号(点击购买题解) 时 间
算法最快[$0 $ms] 大喵-sama 900425 2022-10-11 17:26:17
内存最少[$1188 $KB] Faith 740084 2021-04-18 14:58:29
第一AC 方博飞@网络工程142 108628 2017-07-02 15:29:14
第一挑战 方博飞@网络工程142 108628 2017-07-02 15:29:14

赛题来源/所属竞赛 NA N/A

竞赛编号 竞赛名称 竞赛时间 访问比赛
1611 2020-2021-2学期<算法分析与设计> 第9周练习:贪心算法 2021-04-12 08:00:00 请登录