Overview

We count the number of pairs of points whose slope is between \(A\) and \(B\), inclusive. By sorting the points in order of their \(X\)-coordinates, we can convert the slope condition into a comparison of integer values, which allows us to solve the problem in \(O(N\log N)\) time using coordinate compression and a Fenwick Tree.

Analysis

1. Checking All Pairs is Too Slow

There are \(\frac{N(N-1)}{2}\) pairs of distinct points. Calculating the slope for every pair takes \(O(N^2)\) time, which will not finish in time for \(N=10^5\).

Furthermore, calculating the slope using floating-point numbers may introduce precision errors when comparing with the boundaries \(A\) and \(B\). Therefore, we transform the condition without using division.

2. Sort in Ascending Order of \(X\)-Coordinates

First, sort the points in ascending order of their \(X\)-coordinates. Hereafter, indices represent the order after sorting.

Reordering the points does not change the slope of the line connecting any two points. Therefore, the number of pairs to find also remains unchanged.

Since all \(X\)-coordinates are distinct, if \(i<j\), then \(X_i<X_j\) always holds, which implies \(X_j-X_i>0\).

3. Converting the Slope Condition to an Integer Comparison

Consider the condition for the slope to be at most an integer \(K\):

\(\frac{Y_j-Y_i}{X_j-X_i}\le K\)

Since the denominator is positive, we can multiply both sides by it without reversing the inequality:

\(Y_j-Y_i\le K(X_j-X_i)\)

Rearranging this gives:

\(Y_j-KX_j\le Y_i-KX_i\)

Here, if we define \(V_i=Y_i-KX_i\) for each point, the condition simply becomes \(V_i\ge V_j\).

Similarly, the condition for the slope to be strictly less than \(K\) is \(V_i>V_j\).

Thus, we have reduced the slope condition to the problem of “counting how many values on the left are greater than or equal to, or strictly greater than, the current value.”

4. Computing the Range Condition by Difference of Counts

The desired answer is given by the difference:

\(\text{Answer}=(\text{number of pairs with slope } \le B)-(\text{number of pairs with slope } < A)\)

If we subtract the number of pairs with slope at most \(A\), we would also exclude pairs with slope exactly \(A\). For the lower bound, we must count pairs with slope strictly less than \(A\).

Algorithm

1. Sort the Points

Sort all points in ascending order of their \(X\)-coordinates.

2. Count the Number of Pairs for Bound \(K\)

In the code, count_slopes(bound, strict) returns the following:

• strict = false: number of pairs with slope at most bound
• strict = true: number of pairs with slope strictly less than bound

Specifically, it performs the following steps:

Generate Values and Coordinate Compress

Compute \(V_i=Y_i-KX_i\) for each point.

Since \(V_i\) can be a large integer, its value cannot directly be used as an array index. Therefore, we sort the values, remove duplicates, and assign indices \(0,1,2,\dots\) in ascending order. This is coordinate compression.

Because the relative order and equalities are preserved, we can perform all subsequent comparisons using the compressed indices.

Maintain Values on the Left with a Fenwick Tree

A Fenwick Tree is a data structure that maintains the occurrence counts of each index and can find the sum of occurrences before a given index in \(O(\log N)\) time.

We process the points from left to right. Letting \(i\) be the index of the current point, the preceding \(i\) points have already been inserted into the Fenwick Tree.

Let rank be the compressed index of the current value. In the code, prefix_sum(r) returns the number of occurrences of values with indices from \(0\) up to (but not including) \(r\).

• When the slope is at most \(K\)

We count pairs where the value on the left is greater than or equal to the current value.

There are \(i\) values in total on the left, and among them, the number of values strictly less than the current value is prefix_sum(rank). Therefore, the count to add is:

\(i-\texttt{prefix\_sum(rank)}\)

• When the slope is strictly less than \(K\)

We count pairs where the value on the left is strictly greater than the current value.

We only need to subtract the number of values less than or equal to the current value, so the count to add is:

\(i-\texttt{prefix\_sum(rank+1)}\)

For example, if the registered values are \([2,5,5]\) and the current value is \(5\), there are \(2\) values greater than or equal to the current value, and \(0\) values strictly greater than the current value. As shown, whether equal values are included changes the result.

After adding the count, we insert the current value into the Fenwick Tree. This ensures that each pair is counted exactly once when processing the point on the right.

3. Subtract the Two Results

Finally, output:

count_slopes(B, false) - count_slopes(A, true)

Complexity

• Time Complexity: \(O(N\log N)\)
• Space Complexity: \(O(N)\)

Sorting the points, coordinate compression in each call, and aggregating with the Fenwick Tree all take \(O(N\log N)\) time. Calling the function twice does not change the overall asymptotic complexity.

Implementation Notes

• Pay attention to equality at boundaries
  The upper bound requires “at most \(B\)”, while the subtracted lower bound requires “strictly less than \(A\)”. The code toggles this distinction using strict. Even if \(A=B\), pairs whose slope is exactly that value are counted correctly.

• Query before inserting
  If you insert the current value first, you might count a pair of the point with itself. Always call add(rank) after querying the count.

• Use 64-bit integers
  The absolute value of \(Y_i-KX_i\) can reach up to around \(10^{18}+10^9\). In addition, the answer can be up to \(\frac{N(N-1)}{2}\), which does not fit in a 32-bit integer. Use long long for coordinates, bounds, transformed values, and the answer.

• No floating-point numbers needed
  Everything can be handled using integer arithmetic and comparisons, avoiding precision errors in slope calculations.

  Source Code

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

struct Fenwick {
    int n;
    vector<int> bit;

    explicit Fenwick(int n) : n(n), bit(n + 1, 0) {}

    void add(int i) {
        for (++i; i <= n; i += i & -i) {
            ++bit[i];
        }
    }

    int prefix_sum(int r) const {
        int result = 0;
        for (; r > 0; r -= r & -r) {
            result += bit[r];
        }
        return result;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    ll A, B;
    cin >> N >> A >> B;

    vector<pair<ll, ll>> points(N);
    for (auto& [x, y] : points) {
        cin >> x >> y;
    }
    sort(points.begin(), points.end());

    auto count_slopes = [&](ll bound, bool strict) -> ll {
        vector<ll> values(N);
        for (int i = 0; i < N; ++i) {
            values[i] = points[i].second - bound * points[i].first;
        }

        vector<ll> compressed = values;
        sort(compressed.begin(), compressed.end());
        compressed.erase(unique(compressed.begin(), compressed.end()),
                         compressed.end());

        Fenwick fw(static_cast<int>(compressed.size()));
        ll result = 0;

        for (int i = 0; i < N; ++i) {
            int rank = static_cast<int>(
                lower_bound(compressed.begin(), compressed.end(), values[i])
                - compressed.begin()
            );

            result += i - fw.prefix_sum(rank + (strict ? 1 : 0));
            fw.add(rank);
        }
        return result;
    };

    cout << count_slopes(B, false) - count_slopes(A, true) << '\n';
    return 0;
}

---

This editorial was generated by gpt-6-astra-medium.