概要

\(N\) 個の点から \(2\) 点を選んだときの直線の傾きが \([A, B]\) に入る組の個数を数える問題です。傾きの条件を「\(2\) つの値に関する順序条件」に言い換えることで、BIT（Fenwick Tree）による転倒数カウントの形に落とし込めます。

考察

素朴なアプローチ

すべての組 \((i, j)\) を全探索すると \(O(N^2)\) で、\(N = 10^5\) では約 \(5 \times 10^9\) 通りとなり間に合いません。また、傾き \(\frac{Y_j - Y_i}{X_j - X_i}\) を浮動小数点で計算すると誤差で WA になる危険があります。割り算は使わず、掛け算の形に直すのが基本方針です。

条件式の変形

\(X_i < X_j\) となるように名前を付けます（\(X\) 座標はすべて異なるので、どちらかが小さいと必ず決まります）。このとき \(X_j - X_i > 0\) なので、不等式に \(X_j - X_i\) を掛けても向きは変わりません。

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

左側と右側を分けて整理します。

• 左側: \(A X_j - A X_i \le Y_j - Y_i \iff Y_i - A X_i \le Y_j - A X_j\)
• 右側: \(Y_j - Y_i \le B X_j - B X_i \iff Y_j - B X_j \le Y_i - B X_i\)

そこで各点に対して

\[u_i = Y_i - A X_i, \qquad v_i = Y_i - B X_i\]

と定義すると、条件は

\[u_i \le u_j \quad \text{かつ} \quad v_i \ge v_j\]

というきれいな形になりました。つまり「\(u\) が増えて \(v\) が減る（減らない）ような点のペア」を数えればよいのです。

\(X\) の順序を気にしなくてよいこと

上の式は「\(X\) の小さい方を \(i\)」として導いたものですが、実は \(X\) の順序を無視して「\(u\) について昇順に並べて数える」だけで正しく数えられます。理由を確認しましょう。あるペア \(\{i, j\}\)（\(X_i < X_j\)、傾きを \(s\) とする）について、

• 逆向きの条件 \(u_j \le u_i\) かつ \(v_j \ge v_i\) が成り立つのは \(s \le A\) かつ \(s \ge B\) のとき、つまり \(A = B = s\) のときだけです。

そしてこの場合はもとの条件も満たされています。したがって「\(2\) つのラベル付けのどちらかで \(u\) 昇順・\(v\) 降順になっている」ことと「傾きが \([A,B]\) に入る」ことは同値であり、\(u\) でソートして数えても重複や漏れは起きません。

さらに、\(u_i = u_j\) のときは傾きがちょうど \(A\) であり、\(A \le B\) より必ず条件を満たします（このとき \(v_i \ge v_j\) も自動的に成立します）。

アルゴリズム

1. 各点について \(u_i = Y_i - A X_i\)、\(v_i = Y_i - B X_i\) を計算する。
2. 点を \(u\) の昇順にソートする。\(u\) が等しいときは \(v\) の降順にする（後述）。
3. \(v\) の値を座標圧縮し、BIT を用意する。
4. ソート順に点を見ていき、現在の点 \(q\) について「すでに挿入済みの点のうち \(v \ge v_q\) を満たす個数」を答えに足し、その後 \(v_q\) を BIT に挿入する。
   • \(v \ge v_q\) の個数は、（挿入済みの総数）\(-\)（\(v < v_q\) の個数）で求められる。BIT では \([0, \text{pos})\) の和が \(v < v_q\) の個数。

これは「転倒数」を数えるのと本質的に同じ処理です。

タイブレークの理由: \(u\) が等しいペアは必ず数えたいので、\(v\) 降順に並べておけば、先に来る点 \(p\) について \(v_p \ge v_q\) が必ず成り立ち、確実にカウントされます（\(v\) も等しい場合はどちらの順でも \(v_p \ge v_q\) なので問題ありません）。

具体例

\(A = 1, B = 2\)、点が \((0,0), (1,1), (2,4)\) の場合。

点	\(u = Y - X\)	\(v = Y - 2X\)
1: \((0,0)\)	\(0\)	\(0\)
2: \((1,1)\)	\(0\)	\(-1\)
3: \((2,4)\)	\(2\)	\(0\)

ソート順は点1 \((0,0)\)、点2 \((0,-1)\)、点3 \((2,0)\)。 - 点1を挿入。 - 点2: \(v \ge -1\) の個数 \(= 1\)（点1）→ ペア \((1,2)\)、傾き \(1\) ✓ - 点3: \(v \ge 0\) の個数 \(= 1\)（点1のみ、点2は \(-1\)）→ ペア \((1,3)\)、傾き \(2\) ✓

合計 \(2\)。実際、\((2,3)\) の傾きは \(3\) で範囲外なので正解です。

計算量

• 時間計算量: \(O(N \log N)\)（ソートと BIT の操作）
• 空間計算量: \(O(N)\)

実装のポイント

• オーバーフロー: \(u_i = Y_i - A X_i\) は絶対値が最大 \(10^9 + 10^9 \times 10^9 \approx 10^{18}\) になるため、64bit 整数（long long）が必須です。答えも最大 \(\binom{10^5}{2} \approx 5 \times 10^9\) なので long long で持ちます。

• 割り算を使わない: 傾きを直接計算せず、\(u, v\) への変換で整数比較に持ち込むことで誤差を完全に回避します。

• 座標圧縮: \(v\) の値は巨大なので、ソート＋unique＋lower_bound で \(0\) 以上 \(M\) 未満の添字に置き換えてから BIT に載せます。

• ソートの比較関数: \(u\) 昇順、\(u\) が同じなら \(v\) 降順。ここを間違えると \(u\) が等しいペア（傾きがちょうど \(A\)）の数え方がずれます。

• 「\(v \ge v_q\) の個数」を直接求める代わりに「挿入済み総数 \(-\) \(v < v_q\) の個数」とすると、BIT の実装が接頭辞和だけで済み楽です。

  ソースコード

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

struct BIT {
    int n;
    vector<int> t;
    BIT(int n_) : n(n_), t(n_ + 1, 0) {}
    void add(int i, int x) { for (++i; i <= n; i += i & (-i)) t[i] += x; }
    int sum(int i) { // sum of [0, i)
        int s = 0;
        for (; i > 0; i -= i & (-i)) s += t[i];
        return s;
    }
};

int main() {
    int N;
    long long A, B;
    if (scanf("%d %lld %lld", &N, &A, &B) != 3) return 0;
    vector<long long> X(N), Y(N);
    for (int i = 0; i < N; i++) {
        long long x, y;
        scanf("%lld %lld", &x, &y);
        X[i] = x; Y[i] = y;
    }
    vector<long long> u(N), v(N);
    for (int i = 0; i < N; i++) {
        u[i] = Y[i] - A * X[i];
        v[i] = Y[i] - B * X[i];
    }
    vector<int> idx(N);
    for (int i = 0; i < N; i++) idx[i] = i;
    sort(idx.begin(), idx.end(), [&](int a, int b) {
        if (u[a] != u[b]) return u[a] < u[b];
        return v[a] > v[b]; // ties in u: v descending
    });

    // compress v
    vector<long long> vs = v;
    sort(vs.begin(), vs.end());
    vs.erase(unique(vs.begin(), vs.end()), vs.end());
    int M = (int)vs.size();

    BIT bit(M);
    long long ans = 0;
    int inserted = 0;
    for (int k = 0; k < N; k++) {
        int i = idx[k];
        int pos = (int)(lower_bound(vs.begin(), vs.end(), v[i]) - vs.begin());
        // count previously inserted with v >= v[i]
        int lessCnt = bit.sum(pos); // sum of [0,pos) => v < v[i]
        ans += (long long)(inserted - lessCnt);
        bit.add(pos, 1);
        inserted++;
    }
    printf("%lld\n", ans);
    return 0;
}

---

この解説は claude5opus-high によって生成されました。