VK Cup 2018 - Round 2
D
Contact ATC
Codeforces
2500
原题
← CE →
翻译中…

Arkady the air traffic controller is now working with $*n*$ planes in the air. All planes move along a straight coordinate axis with Arkady's station being at point $0$ on it. The $*i*$-th plane, small enough to be represented by a point, currently has a coordinate of $*x*_{*i*}$ and is moving with speed $*v*_{*i*}$. It's guaranteed that $*x*_{*i*}·*v*_{*i*} < 0$, i.e., all planes are moving towards the station.

翻译中…

Occasionally, the planes are affected by winds. With a wind of speed $*v*_{*wind*}$ (not necessarily positive or integral), the speed of the $*i*$-th plane becomes $*v*_{*i*} + *v*_{*wind*}$.

翻译中…

According to weather report, the current wind has a steady speed falling inside the range $[ - *w*, *w*]$ (inclusive), but the exact value cannot be measured accurately since this value is rather small — smaller than the absolute value of speed of any plane.

翻译中…

Each plane should contact Arkady at the exact moment it passes above his station. And you are to help Arkady count the number of pairs of planes $(*i*, *j*)$ ($*i* < *j*$) there are such that there is a possible value of wind speed, under which planes $*i*$ and $*j*$ contact Arkady at the same moment. This value needn't be the same across different pairs.

翻译中…

The wind speed is the same for all planes. You may assume that the wind has a steady speed and lasts arbitrarily long.

翻译中…

Input

翻译中…

The first line contains two integers $*n*$ and $*w*$ ($1 ≤ *n* ≤ 100 000$, $0 ≤ *w* < 10^{5}$) — the number of planes and the maximum wind speed.

翻译中…

The $*i*$-th of the next $*n*$ lines contains two integers $*x*_{*i*}$ and $*v*_{*i*}$ ($1 ≤ |*x*_{*i*}| ≤ 10^{5}$, $*w* + 1 ≤ |*v*_{*i*}| ≤ 10^{5}$, $*x*_{*i*}·*v*_{*i*} < 0$) — the initial position and speed of the $*i*$-th plane.

翻译中…

Planes are pairwise distinct, that is, no pair of $(*i*, *j*)$ ($*i* < *j*$) exists such that both $*x*_{*i*} = *x*_{*j*}$ and $*v*_{*i*} = *v*_{*j*}$.

翻译中…

Output

翻译中…

Output a single integer — the number of unordered pairs of planes that can contact Arkady at the same moment.

翻译中…

Note

翻译中…

In the first example, the following $3$ pairs of planes satisfy the requirements:

翻译中…
  • $(2, 5)$ passes the station at time $3 / 4$ with $*v*_{*wind*} = 1$;
  • $(3, 4)$ passes the station at time $2 / 5$ with $*v*_{*wind*} = 1 / 2$;
  • $(3, 5)$ passes the station at time $4 / 7$ with $*v*_{*wind*} = - 1 / 4$.
翻译中…

In the second example, each of the $3$ planes with negative coordinates can form a valid pair with each of the other $3$, totaling $9$ pairs.

翻译中…

样例

Input #1
5 1
-3 2
-3 3
-1 2
1 -3
3 -5
Output #1
3
InputCopy OutputCopy
Input #2
6 1
-3 2
-2 2
-1 2
1 -2
2 -2
3 -2
Output #2
9
InputCopy OutputCopy
题目信息
题号
924D
时间限制
1 s
内存限制
256 MB

题面与样例版权归 Codeforces 及出题人所有;中文翻译由 AI 生成(CI 管线),如有出入请以原文为准。