推倒骨牌
时间限制:1秒 内存限制:256M
【题目描述】
给出 \(n\) 个多米诺骨牌的 \(X\) 坐标以及高度 \(H\),每次你可以选任意一张向左推或向右推,推倒后,会产生连锁反应。也就是说,如果 \(|X[i]-X[j]| <= H[i]\),如果 \(X[i] > X[j]\),则把i向左推倒后,则 \(j\) 也会被推倒,如果 \(X[i] < X[j]\),则把 \(i\) 向右推倒后,\(j\) 也会被推倒。连锁反应是指 \(j\) 倒掉后,凡是在 \(j\) 倒向的方向上能推倒的骨牌,也会推倒,他们倒掉,又会推倒他们够的着的骨牌……。
现在问最少几次就能把所有的骨牌推倒。
【输入格式】
第一行一个整数 \(n\),表示骨牌数量。接下来的 \(n\) 行,每行包含两个整数 \(X[i],H[i]\),表示第 \(i\) 个骨牌的位置和高度。
【输出格式】
一行一个整数,表示推的最少次数。
【输入输出样例】
Input
6
1 1
2 2
3 1
5 1
6 1
8 3
Output
2
【数据限制】
\(100\%\) 的数据满足:\(1≤n≤100000\),\(1≤X[i]≤2^{31}-1,\)0≤H[i]≤10^8$。
【来源】
Mr.he