E - Slope of a Line Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 466 点

問題文

2 次元平面上に N 個の点 1, 2, \dots, N があり、点 i の座標は (X_i, Y_i) です。すべての点の X 座標は互いに異なります。また、整数 A, B が与えられます。

高橋君は、異なる 2 点を結ぶ直線の傾きについて調べています。

1 \le i < j \le N を満たす整数の組 (i, j) のうち、点 i と点 j を結ぶ直線の傾き \frac{Y_j - Y_i}{X_j - X_i} が A 以上 B 以下であるもの、すなわち以下を満たす組の個数を求めてください。

A \le \frac{Y_j - Y_i}{X_j - X_i} \le B

制約

  • 2 \le N \le 10^5
  • -10^9 \le A \le B \le 10^9
  • -10^9 \le X_i, Y_i \le 10^9 (1 \le i \le N)
  • X_i \neq X_j (i \neq j)
  • 入力はすべて整数

入力

入力は以下の形式で標準入力から与えられる。

N A B
X_1 Y_1
X_2 Y_2
\vdots
X_N Y_N

出力

条件を満たす組 (i, j) の個数を 1 行に出力してください。

入力例 1

4 0 2
0 0
1 3
2 2
3 1

出力例 1

2

入力例 2

3 1 2
0 0
2 0
5 0

出力例 2

0

入力例 3

10 -2 3
-5 3
-3 -2
-2 4
0 1
1 -5
3 2
4 -1
6 8
7 0
9 -4

出力例 3

36

入力例 4

25 -50 100
10 -150
-40 200
85 -30
-92 -450
15 60
-12 -80
33 120
58 -210
-77 340
4 15
-61 -110
99 500
-25 75
47 -88
72 230
-83 400
19 -95
-5 0
66 180
-38 -250
2 -10
-49 310
80 -400
-18 65
53 140

出力例 4

296

入力例 5

2 -1000000000 -1000000000
-1000000000 1000000000
-999999999 0

出力例 5

1

Score : 466 pts

Problem Statement

There are N points 1, 2, \dots, N on a two-dimensional plane, where the coordinates of point i are (X_i, Y_i). The X-coordinates of all points are distinct. You are also given integers A and B.

Takahashi is investigating the slopes of lines connecting two distinct points.

Among all pairs of integers (i, j) satisfying 1 \le i < j \le N, find the number of pairs such that the slope of the line connecting point i and point j, \frac{Y_j - Y_i}{X_j - X_i}, is at least A and at most B—that is, pairs satisfying the following:

A \le \frac{Y_j - Y_i}{X_j - X_i} \le B

Constraints

  • 2 \le N \le 10^5
  • -10^9 \le A \le B \le 10^9
  • -10^9 \le X_i, Y_i \le 10^9 (1 \le i \le N)
  • X_i \neq X_j (i \neq j)
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

N A B
X_1 Y_1
X_2 Y_2
\vdots
X_N Y_N

Output

Print the number of pairs (i, j) satisfying the condition in a single line.

Sample Input 1

4 0 2
0 0
1 3
2 2
3 1

Sample Output 1

2

Sample Input 2

3 1 2
0 0
2 0
5 0

Sample Output 2

0

Sample Input 3

10 -2 3
-5 3
-3 -2
-2 4
0 1
1 -5
3 2
4 -1
6 8
7 0
9 -4

Sample Output 3

36

Sample Input 4

25 -50 100
10 -150
-40 200
85 -30
-92 -450
15 60
-12 -80
33 120
58 -210
-77 340
4 15
-61 -110
99 500
-25 75
47 -88
72 230
-83 400
19 -95
-5 0
66 180
-38 -250
2 -10
-49 310
80 -400
-18 65
53 140

Sample Output 4

296

Sample Input 5

2 -1000000000 -1000000000
-1000000000 1000000000
-999999999 0

Sample Output 5

1