now 表示当前已选中的最后一个区间的右端点(初始设为一个极小的值,例如 −109)。left 严格大于 now,则选择该区间,答案计数加 1,并将 now 更新为当前区间的右端点;否则跳过。在一座笔直的公园小道旁,计划安装一排喷泉装置。每个喷泉装置有一个固定的中心坐标 c 和一个喷射半径 r,开启后会湿润从 c−r 到 c+r 的一段路面(包含端点)。为了节约用水,管理员希望开启的喷泉湿润区域没有任何公共点(即不能有重叠,也不能端点相接)。给定所有喷泉的中心坐标和半径,请你计算最多可以同时开启多少个喷泉。
喷泉的数量 n 不超过 105,每个喷泉的中心坐标 c 和半径 r 均为不超过 106 的正整数。
第一行包含一个整数 n,表示喷泉的数量。 接下来的 n 行,每行包含两个整数 c 和 r,分别表示一个喷泉的中心坐标和喷射半径。
Scan the QR code below with WeChat to sign in
First-time scan will create your account automatically
请使用微信扫描下方二维码完成注册