Day 077-Q3 | 三分探索 + 凸包上の二変数最適化

問題

平面上に $N$ 個の点 $P_1, \ldots, P_N$ がある。実数パラメータ $t \in [0, 1]$ を選び、以下の目的関数を最小化する $t$ と最小値を求めよ：

$$f(t) = \max_{1 \le i \le N} \left( t \cdot x_i + (1-t) \cdot y_i \right)$$

精度 $10^{-9}$ で答えよ。

制約

パラメータ	範囲	備考
$N$	$2 \le N \le 2 \times 10^5$	点の数
$x_i, y_i$	$-10^9 \le x_i, y_i \le 10^9$	各点の座標
精度	$10^{-9}$	絶対誤差または相対誤差

入出力例

入力例1

出力例1

3.500000000000

$f(t) = \max(6-6t,\; 2+2t,\; 3)$。直線 $6-6t$ と $2+2t$ の交点 $t=0.5$ で最小値 $3.5$（点 $(3,3)$ が切り上げを防ぐ）。実際の最小は $t=0.5$ で $f(0.5)=3.5$。

概念図: 上包絡線と三分探索

各点 $P_i$ が定義する直線 $t(x_i-y_i)+y_i$ の上包絡線は凸関数。三分探索で最小値を $O(200N)$ で求める。

ヒント

ヒント1（方向性）

$f(t) = \max_i h_i(t)$ は線形関数の最大値なので凸関数。凸関数の最小化には三分探索が使える。

ヒント2（アプローチ）

各点 $P_i = (x_i, y_i)$ は直線 $h_i(t) = (x_i - y_i)t + y_i$ を定義する。$f(t) = \max_i h_i(t)$ の最小値を三分探索で求める。区間 $[0, 1]$ を 200 回繰り返すと精度 $(2/3)^{200} \approx 10^{-35}$ で十分。

ヒント3（ほぼ答え）

def f(t):
    return max(t * xi + (1 - t) * yi for xi, yi in points)

lo, hi = 0.0, 1.0
for _ in range(200):
    m1 = lo + (hi - lo) / 3.0
    m2 = hi - (hi - lo) / 3.0
    if f(m1) <= f(m2):
        hi = m2
    else:
        lo = m1

print(f"{f((lo + hi) / 2.0):.12f}")

模範解答

import sys
input = sys.stdin.readline

def solve():
    N = int(input())
    points = [tuple(map(int, input().split())) for _ in range(N)]

    def f(t):
        return max(t * xi + (1.0 - t) * yi for xi, yi in points)

    lo, hi = 0.0, 1.0
    for _ in range(300):
        m1 = lo + (hi - lo) / 3.0
        m2 = hi - (hi - lo) / 3.0
        if f(m1) <= f(m2):
            hi = m2
        else:
            lo = m1

    ans = f((lo + hi) / 2.0)
    print(f"{ans:.12f}")

solve()

Step-by-Step 解説

Step 1: 問題の変換

$f(t) = \max_i (t x_i + (1-t) y_i)$ を変形すると、各点は直線 $h_i(t) = (x_i - y_i) t + y_i$ を定義する。$f(t)$ はこれら $N$ 本の直線の上包絡線。

Step 2: 凸関数の性質

線形関数の最大値は凸関数。証明: $f(\lambda t_1 + (1-\lambda) t_2) \le \lambda f(t_1) + (1-\lambda) f(t_2)$。

Step 3: 三分探索の区間縮小

各ステップで区間が $2/3$ 倍に縮む。200 回後: $(2/3)^{200} \approx 10^{-35}$。精度 $10^{-9}$ には 70 回でも十分。

Step 4: 計算量

フェーズ	計算量
三分探索の評価回数	$O(200)$
各評価	$O(N)$
合計	$O(200N)$

よくあるミス

ミス	原因	正しい書き方
`<` と `<=` の混同	平坦部のある関数での注意	`f(m1) <= f(m2)` → `hi = m2`
回数が少なすぎ	精度不足	200 回以上推奨
$t \in [0,1]$ 以外を探索	問題の制約を無視	`lo=0.0, hi=1.0`
整数型のまま計算	浮動小数点誤差	`float` への変換を明示

次のステップ

発展問題: $f(t) = \max_i (a_i t^2 + b_i t + c_i)$（凸 2 次関数の上包絡線最小値）
応用: 「三分探索 on 三分探索」で二変数の最適化 $f(t, s)$ が凸ならば適用可
参考: Li Chao Tree による上包絡線の静的・動的管理 $O(\log C)$ per query

Day 077-Q3 — 三分探索 + 凸包上の二変数最適化（Golden Section Search・上包絡線最小値）

問題

制約