E - Marathon Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 466 点

問題文

高橋君は N 人のランナーが参加するマラソン大会の実況を担当しています。

ランナーたちは一直線の無限に長いコース上を、同じ方向に向かって走っています。スタート地点からの距離が大きいほど前方であるとします。最初（時刻 0）において、ランナー i（1 \leq i \leq N）はスタート地点から P_i メートルの位置にいます。各ランナーはその後ずっと一定の速度で走り続け、ランナー i の速度は毎秒 V_i メートルです。すなわち、時刻 t 秒におけるランナー i の位置はスタート地点から P_i + V_i \times t メートルの地点です。

高橋君は、レース中に「追い抜き」が何回発生するかを数えて実況に活かしたいと考えています。「追い抜き」とは次のように定義されます。2 人の異なるランナーの組 \{i, j\} について、時刻 0 においてランナー i がランナー j より後方にいる（すなわち P_i < P_j）にもかかわらず、ある時刻 t > 0 においてランナー i がランナー j より前方にいる（すなわち P_i + V_i \times t > P_j + V_j \times t）とき、これを 1 回の追い抜きと数えます。

すべてのランナーの初期位置は互いに異なり、すべてのランナーの速度も互いに異なります。このことから、どの 2 人のランナーの組についても追い抜きは高々 1 回しか発生しません。具体的には、初期位置が後方のランナーの速度が前方のランナーの速度より大きいときに限り、ちょうど 1 回の追い抜きが発生します。

時刻 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
  • 1 行目には、ランナーの人数を表す整数 N が与えられる。
  • 続く N 行の i 行目（1 \leq i \leq N）には、ランナー i の初期位置 P_i（メートル）と速度 V_i（メートル毎秒）が空白区切りで与えられる。

出力

追い抜きの総回数を 1 行で出力してください。

入力例 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

Score : 466 pts

Problem Statement

Takahashi is commentating a marathon with N runners participating.

The runners are running along an infinitely long straight course, all in the same direction. The greater the distance from the starting point, the further ahead a runner is considered to be. Initially (at time 0), runner i (1 \leq i \leq N) is at a position P_i meters from the starting point. Each runner continues running at a constant speed thereafter, and the speed of runner i is V_i meters per second. That is, at time t seconds, the position of runner i is P_i + V_i \times t meters from the starting point.

Takahashi wants to count how many "overtakes" occur during the race to use in his commentary. An "overtake" is defined as follows: for a pair of two distinct runners \{i, j\}, if runner i is behind runner j at time 0 (i.e., P_i < P_j), yet at some time t > 0 runner i is ahead of runner j (i.e., P_i + V_i \times t > P_j + V_j \times t), this counts as one overtake.

All runners have distinct initial positions, and all runners have distinct speeds. Because of this, for any pair of two runners, at most one overtake can occur. Specifically, exactly one overtake occurs if and only if the runner who starts further behind has a greater speed than the runner who starts further ahead.

Find the total number of overtakes that occur from time 0 to the infinite future.

Constraints

  • 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)
  • All input values are integers

Input

N
P_1 V_1
P_2 V_2
\vdots
P_N V_N
  • The first line contains an integer N, the number of runners.
  • The following N lines each contain, on the i-th line (1 \leq i \leq N), the initial position P_i (in meters) and the speed V_i (in meters per second) of runner i, separated by a space.

Output

Output the total number of overtakes in one line.

Sample Input 1

3
1 3
2 1
3 2

Sample Output 1

2

Sample Input 2

5
10 5
30 1
20 4
50 2
40 3

Sample Output 2

8

Sample Input 3

8
100 80
200 30
150 90
400 10
300 50
250 70
500 20
350 60

Sample Output 3

22