Day 048-Q2 | 多次元凸包・最遠点クエリ（Andrew's Monotone Chain + 三分探索）

問題

平面上の $N$ 点の集合 $P$ と $Q$ 個のクエリが与えられる。各クエリでは点 $q_i$ が与えられ、$P$ 中で $q_i$ に最も遠い点（ユークリッド距離）を答えよ（距離の二乗を出力）。

制約

$1 \le N \le 2 \times 10^5$

$1 \le Q \le 2 \times 10^5$

$|x_i|, |y_i| \le 10^9$

出力: 距離の二乗（整数）

時間制限: 2秒

入出力例

入力例 1

出力例 1

8
32

クエリ1（2,2）→ 最遠点は (0,0),(4,0),(4,4),(0,4) のいずれも距離² = 8
クエリ2（0,0）→ 最遠点は (4,4)、距離² = 32

概念図: 凸包上の最遠点と三分探索の単峰性

ヒント（段階的開示）

ヒント1: 方向性

凸包の性質を使います。$P$ の凸包上の点のみが最遠候補になります。凸包を構築した後、各クエリに対して凸包上の最遠点を三分探索で効率よく探します。

ヒント2: アプローチ

凸包の頂点は反時計回りに並んでいる
クエリ点 $q$ からの距離は凸包上で「単峰性」（一度だけ最大値を持ち、前後は単調）
三分探索で O(log N) で最遠点を特定
Andrew's Monotone Chain: O(N log N) で凸包構築
注意: 凸包が 1 点 or 2 点の場合は個別処理

ヒント3: 三分探索の実装骨格

def farthest_on_hull(hull, qx, qy):
    n = len(hull)
    if n == 1:
        return dist2(hull[0], qx, qy)
    if n == 2:
        return max(dist2(hull[0], qx, qy), dist2(hull[1], qx, qy))

    lo, hi = 0, n - 1
    while hi - lo > 2:
        m1 = lo + (hi - lo) // 3
        m2 = hi - (hi - lo) // 3
        if dist2(hull[m1], qx, qy) < dist2(hull[m2], qx, qy):
            lo = m1 + 1
        else:
            hi = m2 - 1

    return max(dist2(hull[i], qx, qy)
               for i in range(max(0, lo-1), min(n, hi+2)))

模範解答 (Python)

import sys

def solve():
    data = sys.stdin.read().split()
    idx = 0
    N, Q = int(data[idx]), int(data[idx+1]); idx += 2
    pts = []
    for _ in range(N):
        x, y = int(data[idx]), int(data[idx+1]); idx += 2
        pts.append((x, y))

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

    def convex_hull(points):
        points = sorted(set(points))
        n = len(points)
        if n <= 1:
            return points
        lower = []
        for p in points:
            while len(lower) >= 2 and cross(lower[-2], lower[-1], p) <= 0:
                lower.pop()
            lower.append(p)
        upper = []
        for p in reversed(points):
            while len(upper) >= 2 and cross(upper[-2], upper[-1], p) <= 0:
                upper.pop()
            upper.append(p)
        return lower[:-1] + upper[:-1]

    hull = convex_hull(pts)
    n = len(hull)

    def dist2(p, qx, qy):
        return (p[0]-qx)**2 + (p[1]-qy)**2

    def farthest(qx, qy):
        if n == 1:
            return dist2(hull[0], qx, qy)
        if n == 2:
            return max(dist2(hull[0], qx, qy), dist2(hull[1], qx, qy))
        lo, hi = 0, n - 1
        while hi - lo > 2:
            m1 = lo + (hi - lo) // 3
            m2 = hi - (hi - lo) // 3
            if dist2(hull[m1], qx, qy) < dist2(hull[m2], qx, qy):
                lo = m1 + 1
            else:
                hi = m2 - 1
        return max(dist2(hull[i], qx, qy)
                   for i in range(max(0, lo-1), min(n, hi+2)))

    out = []
    for _ in range(Q):
        qx, qy = int(data[idx]), int(data[idx+1]); idx += 2
        out.append(farthest(qx, qy))
    print('\n'.join(map(str, out)))

solve()

Step-by-Step 解説

1Andrew's Monotone Chain で凸包構築
点を x 座標でソートし、下凸包・上凸包を順に構築。各点で「左折」しないなら前の点を削除。O(N log N) で完成。

2最遠点は凸包上にある
距離最大点が内部にある場合、その点より外側の凸包頂点が必ず存在するため、凸包頂点のみを探索すれば十分。

3凸包上の距離の単峰性
凸包は凸（折れ曲がりなし）なため、クエリ点からの距離は「ある頂点付近で最大」という単峰の形状を持つ。これにより三分探索が適用可能。

4三分探索の境界処理
三分探索の終了後、残った範囲を線形スキャン（最大3〜4点）して最遠点を確定。off-by-one を防ぐため ±1 のマージンを持たせる。

計算量

凸包構築: $O(N \log N)$
各クエリ: $O(\log N)$（三分探索）
全体: $O((N + Q) \log N)$
空間: $O(N)$（凸包の頂点数）

よくあるミス

ミス	原因	正しい書き方
内部点を含めて探索	最遠点は凸包頂点のみ	convex_hull の結果のみ使用
三分探索の境界でオーバー	単峰性の崩れ	lo, hi に ±1 マージン
重複点の除去忘れ	凸包アルゴリズムが崩れる	`set(points)` で重複除去
凸包が1点・2点の例外処理	三分探索が失敗	n ≤ 2 の場合を個別処理

次のステップ

発展問題: 動的凸包（点の追加をオンラインで処理）
関連: 回転キャリパー法（最遠点対の O(N) 計算）
応用: 3次元凸包の最遠点クエリ、接線探索

自己評価

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