A5431. Woodcutters
编程题
普及/提高-
知识点
题目描述
小 Susie 每天睡前都会听童话故事。今天的故事讲的是伐木工人,小女孩立即开始想象伐木工人砍树的场景,她想象出了如下描述的情景。
有 $n$ 棵树沿公路排列,它们分别位于坐标 $x_{1}, x_{2}, ..., x_{n}$ 处。每棵树的高度为 $h_{i}$。伐木工人可以砍倒一棵树,使其向左或向右倒下。倒下后,树将占据区间 $[x_{i} - h_{i}, x_{i}]$ 或 $[x_{i}, x_{i} + h_{i}]$。未倒下的树只占据 $x_{i}$ 这一个点。如果被倒下的树所占据的区间内没有任何已被占据的点,则可以砍倒这棵树。伐木工人想要砍倒尽可能多的树,Susie 想知道最多可以砍倒多少棵树。
有 $n$ 棵树沿公路排列,它们分别位于坐标 $x_{1}, x_{2}, ..., x_{n}$ 处。每棵树的高度为 $h_{i}$。伐木工人可以砍倒一棵树,使其向左或向右倒下。倒下后,树将占据区间 $[x_{i} - h_{i}, x_{i}]$ 或 $[x_{i}, x_{i} + h_{i}]$。未倒下的树只占据 $x_{i}$ 这一个点。如果被倒下的树所占据的区间内没有任何已被占据的点,则可以砍倒这棵树。伐木工人想要砍倒尽可能多的树,Susie 想知道最多可以砍倒多少棵树。
输入格式
第一行包含一个整数 $n$($1 \le n \le 10^{5}$),表示树的数量。
接下来的 $n$ 行,每行包含一对整数 $x_i, h_i$($1 \le x_i, h_i \le 10^{9}$),表示第 $i$ 棵树的坐标和高度。
这些对数以 $x_i$ 升序给出。不会有两棵树处于相同的坐标。
接下来的 $n$ 行,每行包含一对整数 $x_i, h_i$($1 \le x_i, h_i \le 10^{9}$),表示第 $i$ 棵树的坐标和高度。
这些对数以 $x_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