概要

傾きが \(A\) 以上 \(B\) 以下になる点の組を数えます。点を \(X\) 座標順に並べると、傾きの条件を整数値の大小比較に変換でき、座標圧縮と Fenwick Tree によって \(O(N\log N)\) 時間で求められます。

考察

1. すべての組を調べる方法では間に合わない

異なる \(2\) 点の組は \(\frac{N(N-1)}{2}\) 個あります。すべての組について傾きを計算すると \(O(N^2)\) 時間かかり、\(N=10^5\) では間に合いません。

また、傾きを浮動小数点数で計算すると、境界である \(A\) や \(B\) との比較で誤差が生じる可能性があります。そこで、割り算を使わずに条件を変形します。

2. \(X\) 座標の昇順に並べる

まず、点を \(X\) 座標の昇順にソートします。以降の添字は、ソート後の順序を表すものとします。

点の順番を入れ替えても、同じ \(2\) 点を結ぶ直線の傾きは変わりません。そのため、求める組の個数も変わりません。

すべての \(X\) 座標は異なるので、\(i<j\) なら必ず \(X_i<X_j\) となり、\(X_j-X_i>0\) です。

3. 傾きの条件を整数値の比較に変える

ある整数 \(K\) に対して、傾きが \(K\) 以下になる条件を考えます。

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

分母が正なので、不等号の向きを変えずに両辺に掛けられます。

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

これを整理すると、

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

となります。ここで、各点について \(V_i=Y_i-KX_i\) と定義すると、条件は単に \(V_i\ge V_j\) になります。

同様に、傾きが \(K\) 未満になる条件は \(V_i>V_j\) です。

つまり、傾きの問題を「左側にある値のうち、現在の値以上、または現在の値より大きいものを数える問題」に変換できました。

4. 区間の条件は、個数の差で求める

求める答えは、次の差です。

\(\text{答え}=(\text{傾きが }B\text{ 以下の組数})-(\text{傾きが }A\text{ 未満の組数})\)

\(A\) 以下の組数を引くと、傾きがちょうど \(A\) の組まで除いてしまいます。下限については、必ず「\(A\) 未満」を数える必要があります。

アルゴリズム

1. 点をソートする

すべての点を \(X\) 座標の昇順に並べます。

2. 境界 \(K\) に対する組数を数える

コードの count_slopes(bound, strict) は、次の個数を返します。

• strict = false：傾きが bound 以下の組数
• strict = true：傾きが bound 未満の組数

具体的には、以下の処理を行います。

値を作り、座標圧縮する

各点について \(V_i=Y_i-KX_i\) を計算します。

\(V_i\) は大きな整数になるため、その値をそのまま配列の添字にはできません。そこで、値をソートして重複を除き、小さい順に \(0,1,2,\dots\) の番号を割り当てます。これが座標圧縮です。

大小関係と等しいかどうかは保たれるため、以降は圧縮後の番号で比較できます。

Fenwick Tree で左側の値を管理する

Fenwick Tree は、各番号の出現回数を管理し、ある番号より前の出現回数の合計を \(O(\log N)\) 時間で求められるデータ構造です。

点を左から順に処理します。現在の点の添字を \(i\) とすると、Fenwick Tree には、それより前の \(i\) 個の点を登録しておきます。

現在の値の圧縮後の番号を rank とします。コードの prefix_sum(r) は、番号が \(0\) 以上 \(r\) 未満の値の出現回数を返します。

• 傾きが \(K\) 以下の場合

左側の値が現在の値以上である組を数えます。

左側には全部で \(i\) 個の値があり、そのうち現在の値未満の個数は prefix_sum(rank) なので、加える個数は

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

です。

• 傾きが \(K\) 未満の場合

左側の値が現在の値より大きい組を数えます。

現在の値以下の個数を引けばよいので、加える個数は

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

です。

例えば、登録済みの値が \([2,5,5]\) で現在の値が \(5\) なら、現在の値以上のものは \(2\) 個、現在の値より大きいものは \(0\) 個です。このように、等しい値を含めるかどうかで結果が変わります。

個数を加えた後、現在の値を Fenwick Tree に登録します。これにより、それぞれの組を右側の点の処理時にちょうど一度だけ数えられます。

3. 2 回の計算結果を引く

最後に、

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

を出力します。

計算量

• 時間計算量: \(O(N\log N)\)
• 空間計算量: \(O(N)\)

点のソート、各呼び出しでの座標圧縮、Fenwick Tree による集計はいずれも \(O(N\log N)\) 時間です。関数を \(2\) 回呼び出しても、全体の計算量は変わりません。

実装のポイント

• 境界の等号に注意する
  上限は「\(B\) 以下」、差し引く下限側は「\(A\) 未満」です。コードでは strict によって、この違いを切り替えています。\(A=B\) の場合も、傾きがちょうどその値になる組を正しく数えられます。

• 問い合わせてから登録する
  現在の値を先に登録すると、自分自身との組を数えてしまう可能性があります。必ず個数を求めた後に add(rank) を行います。

• 64 ビット整数を使う
  \(Y_i-KX_i\) の絶対値は最大で \(10^{18}+10^9\) 程度になります。また、答えも最大 \(\frac{N(N-1)}{2}\) となり、32 ビット整数では収まりません。座標、境界、変換後の値、答えには long long を使います。

• 浮動小数点数は不要
  すべて整数の計算と比較で処理できるため、傾きの計算誤差を避けられます。

  ソースコード

#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;
}

---

この解説は gpt-6-astra-medium によって生成されました。