分数: 466 分
问题陈述
高桥正在解说一场马拉松 N 跑步者参与。
跑步者沿着无限长的直线跑道跑步,方向一致。距离起点越远,跑步者就被认为领先得越远。最初(当时 0),跑步者 i (1 \leq i \leq N) 位于某个位置 距起点 P_i 米。此后每个跑步者继续以恒定速度跑步,并且跑步者的速度 i is V_i 米每秒。也就是说,在某个时间 t 秒,跑步者的位置 距起点 i is P_i + V_i \times t 米。
高桥想要计算比赛期间发生了多少次“超车”,以便在他的评论中使用。 “超车”的定义如下:对于两个不同的跑步者 \{i, j\},如果跑步者 i 落后于跑步者 j 时间 0 (即, P_i < P_j),但有时 t > 0 跑步者 i 领先于跑步者 j (即, P_i + V_i \times t > P_j + V_j \times t),这算作一次超车。
所有跑步者都有不同的初始位置,并且所有跑步者都有不同的速度。因此,对于任意两个赛跑者来说,最多只能发生一次超车。具体来说,当且仅当较靠后出发的跑步者比较靠前出发的跑步者速度更快时,才会发生一次超车。
查找从时间开始发生的超车总数 0 走向无限的未来。
约束
- 1 \leq N \leq 2 \times 10^5
- 1 \leq P_i \leq 10^9
- 1 \leq V_i \leq 10^9
- P_i \neq P_j (i \neq j)
- V_i \neq V_j (i \neq j)
- 所有输入值均为整数
输入
N P_1 V_1 P_2 V_2 \vdots P_N V_N
- 第一行包含一个整数 N,跑步者数量。
- 以下 N 行各包含 i- 第行 (1 \leq i \leq N), 初始位置 P_i (以米为单位)和速度 跑步者的 V_i (以米每秒为单位) i,用空格分隔。
输出
输出一行中的超车总数。
示例输入 1
3 1 3 2 1 3 2
示例输出 1
2
示例输入 2
5 10 5 30 1 20 4 50 2 40 3
示例输出 2
8
示例输入 3
8 100 80 200 30 150 90 400 10 300 50 250 70 500 20 350 60
示例输出 3
22