Day 042-Q5 | 半平面交差 + 下凸包（上包絡線最小値）

問題

$N$ 本の直線 $l_i: y = a_i x + b_i$ が与えられる。$\displaystyle\min_{x \in \mathbb{R}} \max_{1 \le i \le N} (a_i x + b_i)$ を求め、その最小値と最小を実現する $x$ 座標を小数点以下6桁で出力せよ。

制約

$1 \le N \le 10^5$

$|a_i|, |b_i| \le 10^9$

すべての $a_i$ は異なる

時間制限: 2sec / メモリ: 256MB

入出力例

入力例 1

出力例 1

0.500000 0.000000

$x=0$ で $\max(x, -x, 1) = 1$ だが、$x=0$ で全直線の上 $\max = 1$。実際は $x=0$ で $(x, -x, 1)=(0,0,1)$ → max=1、三分探索で確認。

概念図: 上包絡線と最小値

ヒント（段階的開示）

ヒント1: 方向性

$f(x) = \max_i(a_i x + b_i)$ は区分線形な凸関数。最小値は凸関数の谷底。三分探索でも解けるが、下凸包を直接構成して $O(N \log N)$ の厳密解が得られる。

ヒント2: アプローチ

直線を傾き $a_i$ でソート。
走査線 + スタックで「下凸包（lower envelope = 上包絡線の最小化）」を構成。
凸包の隣接直線の交点すべてを評価し、最小 $y$ を求める。

注意: Li Chao Tree は最大/最小を $x$ を固定してクエリするもの。ここでは全 $x$ にわたる最小値が欲しいので凸包アプローチが適切。

ヒント3: 実装骨格

lines.sort()  # 傾き昇順

def bad(l1, l2, l3):
    a1,b1 = l1; a2,b2 = l2; a3,b3 = l3
    # l2 が冗長: l1 と l3 の交点が l1 と l2 の交点より左
    return (b3-b1)*(a1-a2) <= (b2-b1)*(a1-a3)

hull = []
for line in lines:
    while len(hull)>=2 and bad(hull[-2], hull[-1], line):
        hull.pop()
    hull.append(line)

# 最小値を求める
best = inf
for i in range(len(hull)-1):
    a1,b1 = hull[i]; a2,b2 = hull[i+1]
    x = (b1-b2)/(a2-a1)  # 交点
    y = a1*x + b1
    best = min(best, y)

模範解答 (Python)

import sys
input = sys.stdin.readline

def solve():
    N = int(input())
    lines = []
    for _ in range(N):
        a, b = map(float, input().split())
        lines.append((a, b))

    # 傾き昇順ソート（同じ傾きは切片大きいものを優先: より上の直線）
    lines.sort(key=lambda x: (x[0], -x[1]))

    def bad(l1, l2, l3):
        """l2 が下凸包から除去されるべきか"""
        a1, b1 = l1; a2, b2 = l2; a3, b3 = l3
        # l1,l2 の交点 x12 = (b1-b2)/(a2-a1)
        # l2,l3 の交点 x23 = (b2-b3)/(a3-a2)
        # x12 >= x23 なら l2 は不要
        # 整理: (b1-b2)*(a3-a2) >= (b2-b3)*(a2-a1)
        return (b1 - b2) * (a3 - a2) >= (b2 - b3) * (a2 - a1)

    hull = []
    for line in lines:
        a, b = line
        # 同じ傾きの処理
        if hull and hull[-1][0] == a:
            if b > hull[-1][1]:
                hull.pop()  # 切片が大きい方（より上）を残す
            else:
                continue
        while len(hull) >= 2 and bad(hull[-2], hull[-1], line):
            hull.pop()
        hull.append(line)

    best_y = float('inf')
    best_x = 0.0

    if len(hull) == 1:
        # 1本のみ: 傾きが 0 なら定数、そうでなければ下限なし
        a, b = hull[0]
        if a == 0:
            best_y = b
            best_x = 0.0
        else:
            # 傾きが0でない1本 → 最小値は -∞ or 傾き=0なら定数
            # 複数直線なら必ず最小は有界
            best_y = b
            best_x = 0.0
    else:
        for i in range(len(hull) - 1):
            a1, b1 = hull[i]
            a2, b2 = hull[i + 1]
            if a2 == a1: continue
            x = (b1 - b2) / (a2 - a1)
            y = a1 * x + b1
            if y < best_y:
                best_y = y
                best_x = x

    print(f"{best_y:.6f} {best_x:.6f}")

solve()

Step-by-Step 解説

1上包絡線の凸性
$f(x) = \max_i(a_i x + b_i)$ は各直線の最大値なので、区分線形かつ凸関数。最小値は必ず隣接する 2 直線の交点で実現される。

2下凸包の構成
傾き昇順にソートした直線を走査線 + スタックで処理。冗長な直線（すでにある 2 直線の交点より左で無効になる直線）をスタックから除去する。

3冗長条件 bad(l1, l2, l3)
$l_1, l_2$ の交点 $x_{12} \ge l_2, l_3$ の交点 $x_{23}$ であれば $l_2$ は冗長（$l_1$ と $l_3$ の直接交点で代替可能）。これをクロス積的に計算する。

4最小値の計算
凸包上の隣接 2 直線の交点すべてを評価し、最小 $y$ を選ぶ。交点は $(a_1 x + b_1 = a_2 x + b_2)$ から $x = (b_1 - b_2)/(a_2 - a_1)$。

計算量

ソート: $O(N \log N)$
凸包構成: $O(N)$（各直線は最大1回スタックに追加・除去）
最小値探索: $O(N)$
合計: $O(N \log N)$

よくあるミス

ミス	原因	正しい書き方
upper/lower envelope の混同	最大化 vs 最小化	min を求めるなら lower envelope
同じ傾きの処理	除去条件の方向	切片が大きい方（より上）を保持
浮動小数点での bad 判定	大きな係数で精度低下	整数係数なら整数演算で行う
N=1 のコーナーケース	凸包が 1 点のみ	傾きが 0 か確認して特別処理

次のステップ

発展問題: 点直線双対変換（点 $(a, b)$ ↔ 直線 $y = ax - b$）による最近傍直線クエリ
類題: Li Chao Tree の "lower envelope" 最小値クエリ
応用: CHT（Convex Hull Trick）による DP 高速化

自己評価

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