#P2111. 2024.9.21-JD-第2题-撞车

2024.9.21-JD-第2题-撞车

题目内容

一条单向单车道的道路上有nn辆车，第ii辆车位于 xix_i;，速度大小为 viv_i 。

显然，如果车辆保持此速度行驶下去，在大多数情况下都会发生碰撞。

现在小塔想知道，至少需要移除几辆车，才能让这些车不发生碰撞?

输入描述

第一行一个整数 n(1≤n≤105)n(1 ≤n≤ 10^5)，表示车的数量。

接下来nn 行，每行两个整数 xi,vi(∣xi∣,∣vi∣,∣vi∣≤109)x_i,v_i(|x_i|,|v_i|,|v_i|≤ 10^9)，表示车的位置和速度的大小。

数据保证 xix_i 互不相同。

输出描述

输出一行一个整数，表示需要移除车的数量。

样例1

输入

3
-1 -1
0 0
1 1

输出

0

说明

样例2

输入

3
-1 1
0 0
1 -1

输出

2

说明

知识点:*****

查看知识点以及同类型题目

Statistics