Overview

This problem asks us to count the number of pairs of points chosen from \(N\) points such that the slope of the line connecting the two points falls within the range \([A, B]\). By applying a coordinate transformation, this reduces to “counting pairs based on a 2D order (counting inversions)”, which can be processed efficiently using a BIT (Fenwick Tree).

Analysis

Naive Approach

Trying all pairs \((i,j)\) takes \(O(N^2)\) time, which requires about \(5 \times 10^9\) operations for \(N = 10^5\) and will not finish in time. Furthermore, calculating the slope using floating-point numbers risks precision errors leading to WA (comparisons should always be done via integer multiplication).

Decomposing the Inequality into “Per-Point Values”

Since \(X_i \ne X_j\), without loss of generality we can assume \(X_i < X_j\) (as swapping \(i\) and \(j\) does not change the slope). Because \(X_j - X_i > 0\), clearing the denominator does not change the direction of the inequalities:

\[A(X_j - X_i) \le Y_j - Y_i \le B(X_j - X_i)\]

Rearranging the left side: $\(Y_i - A X_i \le Y_j - A X_j\)\( Rearranging the right side: \)\(Y_i - B X_i \ge Y_j - B X_j\)$

Here, defining for each point: $\(u_i = Y_i - A X_i,\qquad v_i = Y_i - B X_i\)$ the condition takes the simple form:

\[u_i \le u_j \quad \text{and} \quad v_i \ge v_j \qquad (X_i < X_j)\]

The key takeaway is that this has been transformed into a comparison of two values that can be computed for each point independently.

Why We Can Ignore the Order of \(X\)

We still have the assumption \(X_i < X_j\), but this turns out to be unnecessary. Since \(u_i - v_i = (B-A)X_i\) and \(B \ge A\):

• If \(u_i > u_j\), then \(v_i > v_j\) follows from \(u_i - v_i \le u_j - v_j\) (since \(X_i < X_j\)).
• If \(v_i < v_j\), similarly, \(u_i < u_j\) follows.

Thus, under \(X_i < X_j\), the negation of the condition is restricted to: $\((u_i < u_j \text{ and } v_i < v_j) \quad\text{or}\quad (u_i > u_j \text{ and } v_i > v_j)\)\( These are pairs where \)u\( and \)v\( are **strictly monotonic** in the same direction. Since this condition is symmetric with respect to swapping \)i\( and \)j\(, we can evaluate it without being concerned about the relative order of \)X$.

Therefore,

\[\text{Answer} = \binom{N}{2} - \#\{ \text{pairs } (i,j) : u,v \text{ are both strictly increasing in the same direction} \}\]

(Even when \(A = B\), we have \(u_i = v_i\), which correctly gives “\(\text{Answer} =\) number of pairs such that \(u_i = u_j\)”.)

Algorithm

What we need to count is the “number of pairs such that \(u_i < u_j\) and \(v_i < v_j\)” (so-called concordant pairs). This can be computed using the same technique as counting inversions:

1. For each point, compute \(u_i = Y_i - A X_i\) and \(v_i = Y_i - B X_i\).
2. Sort the points in ascending order of \(u\). However, when \(u\) is equal, sort in descending order of \(v\).
   • This ensures that in the sorted order, the fact that a previous element’s \(v\) is smaller than the current \(v\) directly implies that \(u\) is also strictly smaller (pairs with equal \(u\) will not be counted because their \(v\) values are in descending order).
3. Coordinate compress the values of \(v\), and prepare a BIT (Fenwick Tree, size \(m \le N\)).
4. Traverse in sorted order. For each element, add the count of “already inserted elements whose rank of \(v\) is strictly smaller than the current element” (= prefix sum up to rank \(r-1\)), and then add \(+1\) at the current element’s rank. The sum of these counts gives the number of concordant pairs.
5. Subtract this from \(\binom{N}{2}\) and output the answer.

Small Example

For \(A=0, B=1\) and points \((0,0), (1,2), (2,1)\): \(u = (0, 2, 1)\), \(v = (0, 1, -1)\). - Pair \((1,2)\): \(u: 0 < 2\), \(v: 0 < 1\) \(\to\) same direction \(\to\) does not satisfy the condition (actual slope is \(2\)). - Pair \((1,3)\): \(u: 0 < 1\), \(v: 0 > -1\) \(\to\) satisfies the condition (actual slope is \(0.5\)). - Pair \((2,3)\): \(u: 2 > 1\), \(v: 1 > -1\) \(\to\) same direction \(\to\) does not satisfy the condition (actual slope is \(-1\)).

The answer is \(3 - 2 = 1\), which is correct.

Complexity

• Time Complexity: \(O(N \log N)\) (sorting and BIT operations)
• Space Complexity: \(O(N)\)

Implementation Points

• Overflow: Since \(|Y_i - A X_i| \le 10^9 + 10^9 \cdot 10^9 \approx 10^{18}\), make sure to use long long in languages like C++ (Python supports arbitrary-precision integers, so there is no concern).

• Tie-breaking in sorting: In code, we sort using (u, -v) as the key. This places elements with equal \(u\) in descending order of \(v\), preventing pairs with equal \(u\) from being mistakenly counted. Getting this wrong leads to incorrect handling of pairs whose slope is exactly \(A\) (or \(B\)).

• Coordinate Compression + BIT: Since the values of \(v\) can be up to the scale of \(10^{18}\), they cannot be directly used as array indices. Compress them with sorted(set(...)) to obtain \(1\)-based ranks (as BIT cannot handle index \(0\)).

• Prefix sum range: Since we are counting elements that are “strictly smaller”, for an element of rank \(r\), we query the prefix sum up to \(r-1\) (querying up to \(r\) would include equal values).

• I/O: Since \(N = 10^5\), reading all input at once via sys.stdin.buffer.read() is safe in Python.

• Since no division is performed to compute slopes, precision issues do not arise.

  Source Code

import sys

def main():
    data = sys.stdin.buffer.read().split()
    n = int(data[0]); A = int(data[1]); B = int(data[2])
    X = list(map(int, data[3::2]))
    Y = list(map(int, data[4::2]))

    # u_i = Y_i - A*X_i, v_i = Y_i - B*X_i
    # condition for pair: u_i <= u_j and v_i >= v_j  (orientation implied)
    # answer = C(n,2) - #{pairs with u_i < u_j and v_i < v_j}
    arr = [0] * n
    for i in range(n):
        x = X[i]; y = Y[i]
        arr[i] = (y - A * x, -(y - B * x))
    arr.sort()   # u asc, v desc for ties in u

    vlist = [-t[1] for t in arr]
    sv = sorted(set(vlist))
    idx = {}
    for i, v in enumerate(sv):
        idx[v] = i + 1
    m = len(sv)
    ranks = [idx[v] for v in vlist]

    tree = [0] * (m + 1)
    conc = 0
    for r in ranks:
        s = 0
        p = r - 1
        while p > 0:
            s += tree[p]
            p -= p & (-p)
        conc += s
        p = r
        while p <= m:
            tree[p] += 1
            p += p & (-p)

    sys.stdout.write(str(n * (n - 1) // 2 - conc) + "\n")

main()

---

This editorial was generated by claude5opus-high.