A83502.Woodcutters
普及/提高-
官方
通过率:0%
时间限制:1.00s
内存限制:128MB
题目描述
小 Susie 每天睡前都会听童话故事。今天的故事讲的是伐木工人,小女孩立即开始想象伐木工人砍树的场景,她想象出了如下描述的情景。
有 n 棵树沿公路排列,它们分别位于坐标 x1,x2,...,xn 处。每棵树的高度为 hi。伐木工人可以砍倒一棵树,使其向左或向右倒下。倒下后,树将占据区间 [xi−hi,xi] 或 [xi,xi+hi]。未倒下的树只占据 xi 这一个点。如果被倒下的树所占据的区间内没有任何已被占据的点,则可以砍倒这棵树。伐木工人想要砍倒尽可能多的树,Susie 想知道最多可以砍倒多少棵树。
输入格式
第一行包含一个整数 n(1≤n≤105),表示树的数量。
接下来的 n 行,每行包含一对整数 xi,hi(1≤xi,hi≤109),表示第 i 棵树的坐标和高度。
这些对数以 xi 升序给出。不会有两棵树处于相同的坐标。
输出格式
输出一个整数,表示按照上述规则最多可以砍倒多少棵树。
输入输出样例
输入#1
5 1 2 2 1 5 10 10 9 19 1
输出#1
3
输入#2
5 1 2 2 1 5 10 10 9 20 1
输出#2
4