概要

\(2\) 次元平面上の \(N\) 個の点から \(2\) 点を選んだとき、その直線の傾きが \([A, B]\) の範囲内にあるペアの個数を求める問題です。

不等式を変形することで、\(2\) 次元の点群における大小関係（転倒数に類似した数え上げ）に帰着でき、ソートと Binary Indexed Tree (BIT) を用いて \(O(N \log N)\) で解くことができます。

---

考察

素朴なアプローチとその限界

すべての異なる \(2\) 点の組 \((i, j)\)（\(1 \le i < j \le N\)）について傾きを直接計算すると、調べるペアの総数は \(\frac{N(N - 1)}{2}\) 通りとなります。 本問の制約は \(N \le 10^5\) であるため、ペアの数は約 \(5 \times 10^9\) となり、制限時間内に計算が終わらず TLE (実行時間超過) となってしまいます。したがって、\(O(N^2)\) より高速なアルゴリズムが必要です。

不等式の変形

すべての点の \(X\) 座標は互いに異なるため、\(X_i < X_j\) である点 \(i, j\) のペアについて考えます（一般性を失いません）。 このとき \(X_j - X_i > 0\) であるため、傾きの条件式

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

の両辺に \(X_j - X_i\) を掛けると、不等号の向きを変えずに分母を払うことができます。

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

この不等式を、左側と右側の \(2\) つに分解してそれぞれ整理します。

1. 左側の不等式: $\(A(X_j - X_i) \le Y_j - Y_i \iff Y_i - A X_i \le Y_j - A X_j\)$
2. 右側の不等式: $\(Y_j - Y_i \le B(X_j - X_i) \iff B X_i - Y_i \le B X_j - Y_j\)$

ここで、各点 \(k\) に対して新しい値 \(U_k, W_k\) を以下のように定義します。 - \(U_k = Y_k - A X_k\) - \(W_k = B X_k - Y_k\)

すると、条件は 「\(U_i \le U_j\) かつ \(W_i \le W_j\)」 と非常にシンプルな \(2\) 変数の大小関係に言い換えることができます。

\(X_i < X_j\) という条件について

「\(X_i < X_j\)」という制約を忘れていないか疑問に思うかもしれません。しかし、\(A < B\) のとき、この条件は自動的に満たされます。 なぜなら、

\[ (U_j - U_i) + (W_j - W_i) = (B - A)(X_j - X_i) \]

となるため、\(U_i \le U_j\) かつ \(W_i \le W_j\) であれば、左辺の和は \(0\) 以上になります。 問題文より \(X_i \neq X_j\) であり、\(B - A > 0\) なので、左辺の和が \(0\) になることはなく、必ず正になります。よって自動的に \(X_j - X_i > 0\) （すなわち \(X_i < X_j\)）が保証されます。

したがって、各点を \((U_i, W_i)\) という \(2\) 次元平面上の点と見なしたとき、「\(U_i \le U_j\) かつ \(W_i \le W_j\) を満たすペア \((i, j)\) の個数」 を数えればよいことになります。

※ \(A = B\) の場合は \(B - A = 0\) となり、傾きがちょうど \(A\) である直線を考えることになるため、別処理（\(U_i = U_j\) となるペアをハッシュマップ等で数える）とすると簡単です。

---

アルゴリズム

「\(U_i \le U_j\) かつ \(W_i \le W_j\) を満たすペア」を数え上げる典型手法を用います。

1. \(A = B\) の場合:

   • 各点について \(U_i = Y_i - A X_i\) を計算します。
   • 同じ \(U\) の値を持つ点の個数をハッシュマップでカウントします。
   • 各グループのサイズを \(c\) とすると、\(\frac{c(c - 1)}{2}\) を合計したものが答えになります。

2. \(A < B\) の場合:

   • 各点について \(U_i = Y_i - A X_i\) および \(W_i = B X_i - Y_i\) を計算し、ペア \((U_i, W_i)\) を作成します。
   • \(W\) の値は範囲が広いため、座標圧縮を行って \(1 \le W'_i \le N\) の整数に変換します。
   • 点群を \(U\) の昇順（\(U\) が同じ場合は \(W\) の昇順）にソートします。
   • 順に点を走査しながら、Binary Indexed Tree (BIT) を使って以下を行います：
     1. 現在の点の圧縮後の値を \(r\) としたとき、BIT から \(r\) 以下の値の個数を取得して答えに加算する（この時点で処理済みの点はすべて \(U\) が現在の点以下です）。
     2. BIT の位置 \(r\) に \(1\) を加算する。

---

計算量

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

  • 点のソートに \(O(N \log N)\) かかります。
  • \(W\) の座標圧縮（ソートと重複削除）に \(O(N \log N)\) かかります。
  • BIT に対する要素の追加と区間和クエリは \(1\) 回あたり \(O(\log N)\) であり、全 \(N\) 点に対して行うため \(O(N \log N)\) となります。
  • 全体として \(O(N \log N)\) であり、制限時間内に十分間に合います。

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

  • 点群の座標、座標圧縮用の辞書、BIT の配列を保持するため、\(O(N)\) のメモリを使用します。

---

実装のポイント

• \(A = B\) のコーナーケース: \(A = B\) のとき、\(U_j - U_i\) と \(W_j - W_i\) の和が常に \(0\) になるため、\(U_i \le U_j\) かつ \(W_i \le W_j\) は \(U_i = U_j\)（かつ \(W_i = W_j\)）のときにしか成り立ちません。あらかじめ \(A == B\) の場合を分岐しておくと、バグを防ぎシンプルに実装できます。

• オーバーフローへの配慮: \(X_i, Y_i, A, B\) は最大 \(10^9\) であるため、\(U_i, W_i\) の計算結果は絶対値が最大で約 \(2 \times 10^{18}\) に達します。Python では自動的に多倍長整数として計算されるためオーバーフローの心配はありませんが、C++ などの静的型付け言語を使う場合は long long 型（64bit整数）を使用する必要があります。

  ソースコード

import sys


def solve():
    input_data = sys.stdin.read().split()
    if not input_data:
        return

    N = int(input_data[0])
    A = int(input_data[1])
    B = int(input_data[2])

    if A == B:
        counts = {}
        idx = 3
        for _ in range(N):
            x = int(input_data[idx])
            y = int(input_data[idx + 1])
            idx += 2
            u = y - A * x
            counts[u] = counts.get(u, 0) + 1

        ans = 0
        for c in counts.values():
            ans += c * (c - 1) // 2
        print(ans)
        return

    points = []
    idx = 3
    for _ in range(N):
        x = int(input_data[idx])
        y = int(input_data[idx + 1])
        idx += 2
        u = y - A * x
        w = B * x - y
        points.append((u, w))

    # 座標圧縮 (W について)
    unique_w = sorted(list(set(w for _, w in points)))
    rank = {v: i + 1 for i, v in enumerate(unique_w)}
    m = len(unique_w)

    # U 昇順、タイは W 昇順にソート
    points.sort()

    # Binary Indexed Tree
    tree = [0] * (m + 1)

    def add(i, v):
        while i <= m:
            tree[i] += v
            i += i & (-i)

    def query(i):
        s = 0
        while i > 0:
            s += tree[i]
            i -= i & (-i)
        return s

    ans = 0
    for u, w in points:
        r = rank[w]
        ans += query(r)
        add(r, 1)

    print(ans)


if __name__ == "__main__":
    solve()

---

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