問題
2次元平面上に $N$ 点が与えられる。HULL（凸包の頂点列挙）と FARTHEST u（$P_u$ から最遠の凸包点）クエリに答えよ。
制約
$3 \le N \le 3 \times 10^5$
$1 \le Q \le 10^5$
$|x|, |y| \le 10^9$ 整数
HULL 最大10回 / FARTHEST 最大 $10^5$ 回
入出力例
入力例 1
5
0 0
4 0
4 3
0 3
2 1
5
HULL
FARTHEST 5
FARTHEST 1
FARTHEST 3
HULL出力例 1
1 2 3 4
3
3
1
1 2 3 4ヒント (段階的開示)
ヒント1: 方向性
Andrew's Monotone Chain で凸包構築 $O(N \log N)$、三分探索で最遠点 $O(\log N)$。
ヒント2: アプローチ
凸包は X 座標ソート後に下側・上側を構築。任意点から凸包頂点への距離は単峰なので三分探索可。
ヒント3: 同距離処理
三分探索後は候補範囲を全チェックして最小インデックスを選択。距離は二乗距離（オーバーフロー回避）。
模範解答 (Python)
import sys
input = sys.stdin.readline
def cross(O, A, B):
return (A[0]-O[0])*(B[1]-O[1]) - (A[1]-O[1])*(B[0]-O[0])
def dist2(p, q):
return (p[0]-q[0])**2 + (p[1]-q[1])**2
def build_hull(pts_idx):
sorted_pts = sorted(pts_idx, key=lambda t: (t[1][0], t[1][1]))
lower, upper = [], []
for p in sorted_pts:
while len(lower) >= 2 and cross(lower[-2][1], lower[-1][1], p[1]) <= 0:
lower.pop()
lower.append(p)
for p in reversed(sorted_pts):
while len(upper) >= 2 and cross(upper[-2][1], upper[-1][1], p[1]) <= 0:
upper.pop()
upper.append(p)
return lower[:-1] + upper[:-1]
def farthest_on_hull(hull, p):
n = len(hull)
if n == 1:
return hull[0][0] + 1
lo, hi = 0, n - 1
for _ in range(200):
if lo >= hi - 1:
break
m1 = lo + (hi - lo) // 3
m2 = hi - (hi - lo) // 3
if dist2(hull[m1][1], p) < dist2(hull[m2][1], p):
lo = m1 + 1
else:
hi = m2 - 1
best_d, best_i = -1, float('inf')
for i in range(max(0, lo-1), min(n, hi+2)):
d = dist2(hull[i][1], p)
idx1 = hull[i][0] + 1
if d > best_d or (d == best_d and idx1 < best_i):
best_d, best_i = d, idx1
return best_i
def solve():
N = int(input())
pts = []
for _ in range(N):
x, y = map(int, input().split())
pts.append((x, y))
pts_idx = [(i, pts[i]) for i in range(N)]
hull = build_hull(pts_idx)
Q = int(input())
out = []
for _ in range(Q):
line = input().split()
if line[0] == 'HULL':
out.append(' '.join(str(p[0]+1) for p in hull))
else:
u = int(line[1]) - 1
out.append(str(farthest_on_hull(hull, pts[u])))
print('\n'.join(out))
solve()Step-by-Step 解説
1Andrew's Monotone Chain
X 座標ソート後、下側・上側凸包を別々に構築。
X 座標ソート後、下側・上側凸包を別々に構築。
cross が 0 以下で中間点を削除。2三分探索で最遠点
凸包上で距離は単峰。十分な反復で最大点を $O(\log N)$ 特定。
凸包上で距離は単峰。十分な反復で最大点を $O(\log N)$ 特定。
3同距離処理
候補範囲を全チェック、最小インデックスを選ぶ。
候補範囲を全チェック、最小インデックスを選ぶ。
4クエリ処理
HULL は凸包を 1-indexed で出力、FARTHEST は三分探索。
HULL は凸包を 1-indexed で出力、FARTHEST は三分探索。
よくあるミス
| ミス | 原因 | 正しい書き方 |
|---|---|---|
| cross の符号 | 共線点を含むかで使い分け | 問題に応じて <= 0 / < 0 |
| 三分探索の収束不足 | 反復回数が少ない | 50〜100回 |
| 1/0-indexed 混在 | 入出力変換ミス | 入力直後に統一 |
次のステップ
- 動的点追加に対するオンライン凸包 + 最遠点 $O(\log^2 N)$