← 返回题目列表

AtCoder · awc0057_e

E. 马拉松

中文机器翻译题面 查看原题

分数: 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