概要

\(N\) 個の点から \(2\) 点を選んだとき、その \(2\) 点を結ぶ直線の傾きが \([A, B]\) に入るような組の個数を数える問題です。座標変換によって「2 次元の順序に関する組の数え上げ（転倒数の数え上げ）」に帰着させ、BIT（Fenwick Tree）で高速に処理します。

考察

素朴な方法

すべての組 \((i,j)\) を試すと \(O(N^2)\) で、\(N = 10^5\) では約 \(5 \times 10^9\) 回の計算になり間に合いません。また、傾きを浮動小数点で計算すると誤差で WA になる危険があります（比較は必ず整数の掛け算で行うべきです）。

不等式を「点ごとの値」に分解する

\(X_i \ne X_j\) なので、\(X_i < X_j\) となるように \(i, j\) を決めておきます（傾きは \(i,j\) を入れ替えても変わらないので一般性を失いません）。\(X_j - X_i > 0\) なので、分母を払っても不等号の向きは変わりません。

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

左側を整理すると $\(Y_i - A X_i \le Y_j - A X_j\)\( 右側を整理すると \)\(Y_i - B X_i \ge Y_j - B X_j\)$

ここで各点について $\(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 \qquad (X_i < X_j)\]

というシンプルな形になります。各点ごとに計算できる 2 つの値の大小比較に変わったのがポイントです。

「\(X\) の順序」を気にしなくてよい理由

まだ「\(X_i < X_j\) という前提」が残っていますが、実は不要です。\(u_i - v_i = (B-A)X_i\) であり \(B \ge A\) なので、

• \(u_i > u_j\) ならば \(u_i - v_i \le u_j - v_j\)（\(X_i<X_j\) より）から \(v_i > v_j\) が従う
• \(v_i < v_j\) ならば同様に \(u_i < u_j\) が従う

つまり \(X_i < X_j\) のもとで条件の否定は $\((u_i < u_j \text{ かつ } v_i < v_j) \quad\text{または}\quad (u_i > u_j \text{ かつ } v_i > v_j)\)\( に限られます。これは「\)u\( と \)v\( が同じ向きに**狭義単調**で並んでいる組」であり、\)i,j\( の入れ替えについて対称なので、\)X$ の大小を気にせず判定できます。

よって

\[\text{答え} = \binom{N}{2} - \#\{ \text{組 } (i,j) : u,v \text{ がともに同じ向きに狭義増加している} \}\]

（\(A = B\) の場合も、\(u_i = v_i\) となり「答え \(=\) \(u_i = u_j\) となる組の個数」を正しく与えます。）

アルゴリズム

数えるべきは「\(u_i < u_j\) かつ \(v_i < v_j\) となる組の数」（いわゆる concordant pair の数）です。これは転倒数の数え方と同じ要領で求められます。

1. 各点について \(u_i = Y_i - A X_i\), \(v_i = Y_i - B X_i\) を計算する。
2. \(u\) の昇順にソートする。ただし \(u\) が等しいときは \(v\) の降順にする。
   • こうすると、ソート後の順で「前にある要素の \(v\) より現在の \(v\) が大きい」ことが、そのまま「\(u\) も狭義に小さい」ことを意味します（\(u\) が同じ組は \(v\) が降順なので数え上げられません）。
3. \(v\) の値を座標圧縮し、BIT（Fenwick Tree、要素数 \(m \le N\)）を用意する。
4. ソート順に走査し、各要素について「すでに挿入済みで \(v\) のランクが自分より真に小さい個数」（= ランク \(r-1\) までの prefix sum）を足し込み、その後で自分のランクに \(+1\) する。この総和が concordant pair の数。
5. \(\binom{N}{2}\) から引いて出力する。

小さな例

\(A=0, B=1\)、点 \((0,0), (1,2), (2,1)\) の場合。 \(u = (0, 2, 1)\)、\(v = (0, 1, -1)\)。 - 組 \((1,2)\): \(u:0<2\), \(v:0<1\) → 同じ向き → 条件を満たさない（実際傾き \(2\)）。 - 組 \((1,3)\): \(u:0<1\), \(v:0>-1\) → 満たす（傾き \(0.5\)）。 - 組 \((2,3)\): \(u:2>1\), \(v:1>-1\) → 同じ向き → 満たさない（傾き \(-1\)）。

答えは \(3 - 2 = 1\) で正しいです。

計算量

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

実装のポイント

• オーバーフロー: \(|Y_i - A X_i| \le 10^9 + 10^9 \cdot 10^9 \approx 10^{18}\) なので、C++ 等では必ず long long を使います（Python は多倍長なので安心）。

• ソートのタイブレーク: コードでは (u, -v) をキーにソートしています。これで \(u\) が同じときに \(v\) が降順に並び、\(u\) が等しい組を誤って数えるのを防げます。ここを間違えると、傾きがちょうど \(A\)（または \(B\)）になる組の扱いを誤ります。

• 座標圧縮 + BIT: \(v\) の値は最大 \(10^{18}\) 規模なのでそのままでは添字にできません。sorted(set(...)) で圧縮し、\(1\) 始まりのランクにします（BIT は添字 \(0\) を扱えないため）。

• prefix sum の範囲: 「真に小さい」を数えるので、ランク \(r\) の要素に対して \(r-1\) までの和を取ります（\(r\) までにすると同値を含んでしまいます）。

• 入出力: \(N = 10^5\) なので Python では sys.stdin.buffer.read() による一括読み込みが安全です。

• 傾きの割り算は一切行わないため、精度の問題は発生しません。

  ソースコード

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()

---

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