Contact ATC
Contest: VK Cup 2018 - Round 2
Difficulty rating: 2500

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 xi and is moving with speed vi. It's guaranteed that xi·vi < 0, i.e., all planes are moving towards the station.

Occasionally, the planes are affected by winds. With a wind of speed vwind (not necessarily positive or integral), the speed of the i-th plane becomes vi + vwind.

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 format:
The first line contains two integers n and w (1 ≤ n ≤ 100 000, 0 ≤ w < 105) — the number of planes and the maximum wind speed.

The i-th of the next n lines contains two integers xi and vi (1 ≤ |xi| ≤ 105, w + 1 ≤ |vi| ≤ 105, xi·vi < 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 xi = xj and vi = vj.

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

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

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

- (2, 5) passes the station at time 3 / 4 with vwind = 1;
- (3, 4) passes the station at time 2 / 5 with vwind = 1 / 2;
- (3, 5) passes the station at time 4 / 7 with vwind =  - 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.

Example input:
5 1
-3 2
-3 3
-1 2
1 -3
3 -5

Example output:
3

Example input:
6 1
-3 2
-2 2
-1 2
1 -2
2 -2
3 -2

Example output:
9

Editorial:
Stuck in tedious fractions produced by kinematic formulae? No, that's not the way to go. Forgetting about all physics, how does wind speed affect the time when a plane flies over the origin?
Consider a plane flying from left to right, passing through the origin. Initially it has speed vi - w and meets the origin at time t. As the wind speed goes from  - w to  + w, the plane's speed continually rises to vi + w, with t becoming smaller and smaller (this is true because w < |vi|). The similar holds for planes going from right to left, with the exception that t becomes greater and greater.
Then, how does wind speed affect the order in which a pair of planes pass the origin?
Imagine two planes, A and B. With wind speed  - w, they arrive at the origin at moments tA and tB, respectively. As the wind speed goes from  - w to  + w, tA moves smoothly and so does tB and suddenly... Uh! They become the same! That makes them a valid pair.
From this perspective we can conclude that for such a pair of planes A and B, if A arrives at the origin at moment tA and t'A with wind speed  - w and  + w, and B at tB and t'B respectively, they possibly meet at the origin iff (tA - tB)·(t'A - t'B) ≤ 0.
Oh, what's this? Inversion pairs, of course! Apply wind  - w and  + w to all the planes, find out the orders in which they arrive at the origin under the two winds, and count the pairs (A, B) where A goes before B in the first permutation, and after B in the second one. One detail to note is that in case of ties, pairs should be sorted by descending values of speed in the first pass and ascending in the second (the speeds cannot be the same since all planes are distinct). That leaves us only with a binary indexed tree to be implemented. The overall time complexity is $$O(n \log n)$$.
Please note that it's recommended to use an integer pair to represent a fraction, since the difference between arrival times can be as little as 10 - 10 — though a floating point error tolerance of 5 × 10 - 12 passes all tests, its robustness is not so easy to control.