问题 G: 安全出行

问题 G: 安全出行

时间限制: 1 Sec  内存限制: 128 MB
提交: 705  解决: 220
[状态] [讨论版] [提交] [命题人:]
题目描述
有 N 辆汽车在无限长的单行道上行驶,且行驶方向为坐标值增大的方向。每辆车在跑道上开始行驶的位置互不相同,一些车辆的行驶速度可能相同,也可能不同。由于跑道是单行道,十分狭窄,汽车们无法相互超越。当一辆速度很快的汽车追上另一辆汽车时,他必须减速至与另一辆车速度相同以免发生碰撞,并成为同一车队的一员。此时,两辆车可以视为在同一点上。最终,再也没有汽车会撞到(追上)其他汽车了。
求在这种情况下,会剩下多少个车队。
输入
第一行包含整数N。
接下来N行,每行包含一辆车的初始位置和行驶速度。
所有车辆的初始位置各不相同,且是按照递增顺序给出的。
1<= N <= 1e5
初始位置范围[0 , 1e9]
行驶速度范围[0 , 1e9]
输出
输出一个整数,表示最终剩下的车队数量。
样例输入 Copy
5
0 1
1 2
2 3
3 2
6 1
样例输出 Copy
2