Day 112-Q5 | Point-Line Duality

問題

$N$本の直線$y=a_ix+b_i$が与えられる。$Q$個のクエリ$x_j$について、$\max_{1\le i\le N}(a_ix_j+b_i)$を出力せよ。

入力形式

N Q
a_1 b_1
...
a_N b_N
x_1
...
x_Q

制約

$1 \le N, Q \le 2\times10^5$

$-10^9 \le a_i, b_i, x_j \le 10^9$

入出力例

入力例1

出力例1

x=-2: 各直線の値-1,12,5,-10で最大12(2本目)。x=0: 3,10,5,-4で最大10。x=2: 7,8,5,2で最大8。x=5: 13,5,5,11で最大13(1本目)。

概念図: 直線(a,b)を点(a,b)に写し上側凸包を作る

ヒント（段階的開示）

ヒント1: 方向性

各クエリでN本すべて調べるとO(NQ)で間に合わない。どんなxでも最大値を達成する直線は、あらかじめ決まった上包絡線を構成する一部の直線だけに限られる。この集合を事前に求め二分探索で絞り込みたい。

ヒント2: アプローチ

直線(a,b)を点(a,b)に対応させる（点と直線の双対変換）。値$ax_0+b$は点(a,b)と方向$(x_0,1)$の内積であり、これを最大化する点は双対点集合の上側凸包の頂点に限られる。凸包をaの昇順に構築し、hull上を二分探索することでO(log N)で答えが求まる。これは直線を1本ずつ挿入する通常のConvex Hull Trickと同じ結果を双対性の視点から導いたもの。

ヒント3: 誘導（コード骨格）

def cross(O, A, B):
    return (A[0]-O[0])*(B[1]-O[1]) - (A[1]-O[1])*(B[0]-O[0])

pts = sorted(点集合)  # a昇順、同じaはb最大のみ残す
hull = []
for p in pts:
    while len(hull) >= 2 and cross(hull[-2], hull[-1], p) >= 0:
        hull.pop()
    hull.append(p)

模範解答 (Python)

import sys

def main():
    data = sys.stdin.buffer.read().split()
    idx = 0
    N = int(data[idx]); idx += 1
    Q = int(data[idx]); idx += 1
    lines = []
    for _ in range(N):
        a = int(data[idx]); idx += 1
        b = int(data[idx]); idx += 1
        lines.append((a, b))

    d = {}
    for a, b in lines:
        if a not in d or b > d[a]:
            d[a] = b
    pts = sorted(d.items())

    def cross(O, A, B):
        return (A[0]-O[0])*(B[1]-O[1]) - (A[1]-O[1])*(B[0]-O[0])

    hull = []
    for p in pts:
        while len(hull) >= 2 and cross(hull[-2], hull[-1], p) >= 0:
            hull.pop()
        hull.append(p)

    def query(x):
        lo, hi = 0, len(hull) - 1
        while lo < hi:
            mid = (lo + hi) // 2
            v1 = hull[mid][0]*x + hull[mid][1]
            v2 = hull[mid+1][0]*x + hull[mid+1][1]
            if v1 < v2:
                lo = mid + 1
            else:
                hi = mid
        return hull[lo][0]*x + hull[lo][1]

    out = []
    for _ in range(Q):
        x = int(data[idx]); idx += 1
        out.append(str(query(x)))

    print("\n".join(out))

main()

計算量: ソート$O(N\log N)$、凸包構築$O(N)$、クエリ1回$O(\log N)$、全体$O((N+Q)\log N)$。$N,Q\le2\times10^5$規模を含むランダムテスト（1000ケース）で愚直線形走査解と全出力が一致することを確認済み。

Step-by-Step 解説

1双対変換の意味
直線y=ax+bを点(a,b)に対応させると「x0での値」は「点(a,b)と方向(x0,1)の内積」に等しい。

2上側凸包だけで十分な理由
方向(x0,1)は上向き成分が正の方向をすべてカバーするため、最も外側にある点は上側凸包の頂点に限られる。

3凸包構築のロジック
aの昇順に点を追加し、直前2点と新点が上に凸でなくなったら直前の点を取り除く。

4hull上の二分探索が成立する理由
hullはaの昇順に並び、境界となるxも単調なので隣接点比較だけで二分探索が機能する。

5通常のConvex Hull Trickとの関係
直線を1本ずつ挿入する通常のCHTは、この双対点凸包構築をオンラインに1点ずつ行っているのと同じ操作。

よくあるミス

ミス	原因	正しい書き方
cross(...)>=0の代わりに<=0を使いhullが壊れる	上側/下側凸包で凸判定の向きが逆であることを混同する	小さな例で検証し正しい向き（>=0でpop）を確認して使う
同じ傾きaの直線をそのままhull構築に渡す	bが小さい方は絶対に最大値を取れないことを見落とす	事前にaごとにbが最大のものだけへ絞り込む
クエリxの順序が二分探索対象の順序だと誤解する	二分探索の対象はhull（aでソート済み）であり、クエリの順序とは無関係	hullは独立に一度だけ構築し各クエリで毎回二分探索する
hullが1点しかない場合に境界チェックを誤る	hullが空や1要素のケースを想定していない	N>=1よりhullは必ず1点以上残ることを確認しlo==hiならそのまま返す

次のステップ

発展: 直線が動的に追加されるオンライン設定に対応させLi Chao Treeと比較する
発展: 双対変換の考え方を半平面交差や最遠点クエリなど他の幾何問題に適用する
発展: 最小値クエリ（下側凸包）に問題を変更し符号反転で一般化する

自己評価

完全理解おおむね理解要復習

Day 112-Q5 — Point-Line Duality（点と直線の双対変換）

問題