Overview

The problem asks us to find the number of pairs of points chosen from \(N\) points on a 2D plane such that the slope of the line passing through the two points is between \(A\) and \(B\), inclusive. By rearranging the inequality, this problem can be reduced to finding the number of pairs satisfying “\(u_i \le u_j\) and \(v_i \le v_j\) on a 2D plane,” which can be solved in \(O(N \log N)\) time using sorting and a Binary Indexed Tree (BIT).

Analysis

Naive Approach and Its Limitations

If we compute the slope and check the condition for all pairs \((i, j)\) (\(1 \le i < j \le N\)), the total number of pairs is \(\frac{N(N - 1)}{2} = O(N^2)\). Under the constraint \(N \le 10^5\), this requires about \(5 \times 10^9\) operations, leading to Time Limit Exceeded (TLE). Therefore, we need an approach with a time complexity around \(O(N \log N)\).

Transforming the Inequality

Since the slope of the line connecting two points does not depend on the order of the points, we can assume without loss of generality that \(X_i < X_j\). In this case, the condition for the slope can be expressed as:

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

Since \(X_j - X_i > 0\), we can multiply each side by \(X_j - X_i\) to clear the denominator:

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

We can split this system of inequalities into separate terms for \(i\) and \(j\):

1. Left inequality: \(A(X_j - X_i) \le Y_j - Y_i\) $\(Y_i - A X_i \le Y_j - A X_j\)$
2. Right inequality: \(Y_j - Y_i \le B(X_j - X_i)\) $\(B X_i - Y_i \le B X_j - Y_j\)$

Now, for each point \(k\), let us define two new values \(u_k\) and \(v_k\) as follows: - \(u_k = Y_k - A X_k\) - \(v_k = B X_k - Y_k\)

Then, the condition can be expressed very simply as “\(u_i \le u_j\) and \(v_i \le v_j\)”.

Regarding the Condition \(X_i < X_j\)

Notice that summing \(u_k\) and \(v_k\) yields: $\(u_k + v_k = (Y_k - A X_k) + (B X_k - Y_k) = (B - A) X_k\)$

When \(A < B\), we have \(B - A > 0\). Thus, if \(u_i \le u_j\) and \(v_i \le v_j\) hold, then: $\(u_i + v_i \le u_j + v_j \iff (B - A)X_i \le (B - A)X_j \iff X_i \le X_j\)\( is **automatically satisfied**. Since all points have distinct \)X\(-coordinates, \)i \neq j\( implies \)X_i < X_j\( strictly. In other words, we do not need to explicitly check the relative order of the \)X\(-coordinates; the problem simply reduces to counting the number of pairs satisfying "\)u_i \le u_j\( and \)v_i \le v_j$” (which is counting comparable pairs in a 2D poset, a generalization of inversion counting).

When \(A = B\)

When \(A = B\), we have \(B - A = 0\), and we are counting pairs whose slope is exactly equal to \(A\). In this case, it suffices to count the number of pairs with \(u_i = u_j\) (i.e., \(Y_i - A X_i = Y_j - A X_j\)).

Algorithm

1. When \(A = B\)

1. For each point, compute \(u_i = Y_i - A X_i\).
2. Sort the values of \(u_i\). For each group of points with the same value of size \(k\), compute \(\frac{k(k-1)}{2}\) and add it to the answer.

2. When \(A < B\)

1. For each point, compute \(u_i = Y_i - A X_i\) and \(v_i = B X_i - Y_i\).
2. Since the range of \(v_i\) can be large, apply coordinate compression to map the values to \(0\)-indexed integers.
3. Sort the points in ascending order of \(u\) (breaking ties by sorting by \(v\) in ascending order).
4. Iterate through the points in sorted order:
   • Using a Binary Indexed Tree (BIT), query the number of previously processed points with a value less than or equal to the current \(v_i\), and add this count to the answer.
   • Insert the current \(v_i\) into the BIT (increment its count by \(+1\)).

This allows us to count all pairs \((i, j)\) satisfying the conditions without duplicates.

Complexity

• Time Complexity: \(O(N \log N)\)
  • Computing \(u_i, v_i\) for each point takes \(O(N)\).
  • Coordinate compression and sorting the points take \(O(N \log N)\).
  • \(N\) additions and queries on the BIT take \(O(N \log N)\).
  • Overall, the time complexity is \(O(N \log N)\), which easily runs within the time limit.
• Space Complexity: \(O(N)\)
  • The point coordinates, transformed values, coordinate compression array, and BIT all require \(O(N)\) space.

Implementation Notes

• Beware of Overflow: Since the absolute values of the coordinates \(X_i, Y_i\) and the slopes \(A, B\) can be up to \(10^9\), products such as \(A X_i\) can reach up to approximately \(10^{18}\). Since this overflows a 32-bit integer, be sure to use 64-bit integers (e.g., long long in C++) for the computations. Furthermore, the total answer can be up to \(\frac{N(N-1)}{2} \approx 5 \times 10^9\), so the variable storing the answer must also be a long long.

• Tie-breaking when \(u\) is equal: When \(u_i = u_j\), sorting by \(v\) in ascending order as the secondary key ensures that pairs with \(u_i = u_j\) and \(v_i \le v_j\) are correctly counted by processing the smaller \(v\) element first in the BIT.

  Source Code

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

struct BIT {
    int n;
    vector<int> tree;
    BIT(int n) : n(n), tree(n + 1, 0) {}
    void add(int i, int delta) {
        for (++i; i <= n; i += i & -i) tree[i] += delta;
    }
    int query(int i) { // sum [0, i]
        int sum = 0;
        for (++i; i > 0; i -= i & -i) sum += tree[i];
        return sum;
    }
};

struct Point {
    long long u, v;
};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    long long a, b;
    if (!(cin >> n >> a >> b)) return 0;

    vector<long long> x(n), y(n);
    for (int i = 0; i < n; ++i) {
        cin >> x[i] >> y[i];
    }

    if (a == b) {
        vector<long long> u(n);
        for (int i = 0; i < n; ++i) {
            u[i] = y[i] - a * x[i];
        }
        sort(u.begin(), u.end());
        long long ans = 0;
        long long count = 1;
        for (int i = 1; i < n; ++i) {
            if (u[i] == u[i - 1]) {
                count++;
            } else {
                ans += count * (count - 1) / 2;
                count = 1;
            }
        }
        ans += count * (count - 1) / 2;
        cout << ans << "\n";
        return 0;
    }

    vector<Point> pts(n);
    vector<long long> vals(n);
    for (int i = 0; i < n; ++i) {
        pts[i].u = y[i] - a * x[i];
        pts[i].v = b * x[i] - y[i];
        vals[i] = pts[i].v;
    }

    sort(vals.begin(), vals.end());
    vals.erase(unique(vals.begin(), vals.end()), vals.end());

    sort(pts.begin(), pts.end(), [](const Point& p1, const Point& p2) {
        if (p1.u != p2.u) return p1.u < p2.u;
        return p1.v < p2.v;
    });

    BIT bit(vals.size());
    long long ans = 0;
    for (int i = 0; i < n; ++i) {
        int id = lower_bound(vals.begin(), vals.end(), pts[i].v) - vals.begin();
        ans += bit.query(id);
        bit.add(id, 1);
    }

    cout << ans << "\n";

    return 0;
}

---

This editorial was generated by gemini-3.8-flash-high.