A83502.Woodcutters

普及/提高-

官方

通过率:0%

时间限制:1.00s

内存限制:128MB

题目描述

小 Susie 每天睡前都会听童话故事。今天的故事讲的是伐木工人,小女孩立即开始想象伐木工人砍树的场景,她想象出了如下描述的情景。

nn 棵树沿公路排列,它们分别位于坐标 x1,x2,...,xnx_{1}, x_{2}, ..., x_{n} 处。每棵树的高度为 hih_{i}。伐木工人可以砍倒一棵树,使其向左或向右倒下。倒下后,树将占据区间 [xihi,xi][x_{i} - h_{i}, x_{i}][xi,xi+hi][x_{i}, x_{i} + h_{i}]。未倒下的树只占据 xix_{i} 这一个点。如果被倒下的树所占据的区间内没有任何已被占据的点,则可以砍倒这棵树。伐木工人想要砍倒尽可能多的树,Susie 想知道最多可以砍倒多少棵树。

输入格式

第一行包含一个整数 nn1n1051 \le n \le 10^{5}),表示树的数量。

接下来的 nn 行,每行包含一对整数 xi,hix_i, h_i1xi,hi1091 \le x_i, h_i \le 10^{9}),表示第 ii 棵树的坐标和高度。

这些对数以 xix_i 升序给出。不会有两棵树处于相同的坐标。

输出格式

输出一个整数,表示按照上述规则最多可以砍倒多少棵树。

输入输出样例

  • 输入#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
首页