問題
平面上に $N$ 点が与えられる。これらの点を囲む凸包の周長を求めよ。
制約
$3 \le N \le 10^5$
$-10^9 \le x_i, y_i \le 10^9$
すべての点が一直線上に乗らない
同じ座標の点はない
入出力例
入力例 1
5
0 0
4 0
4 3
0 4
2 2出力例 1
14.472135954999579ヒント (段階的開示)
ヒント1: 方向性
Andrew's Monotone Chain で $O(N \log N)$。下側凸包と上側凸包を別々に構築して結合。
ヒント2: アプローチ
外積の符号で左折り/右折りを判定。右折りになる点はスタックから除去。
ヒント3: 誘導
while len(lower) >= 2 and cross(lower[-2], lower[-1], p) <= 0:
lower.pop()
lower.append(p)模範解答 (Python)
import math
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]
def dist(p1, p2):
return math.sqrt((p1[0]-p2[0])**2 + (p1[1]-p2[1])**2)
def solve():
N = int(input())
points = []
for _ in range(N):
x, y = map(int, input().split())
points.append((x, y))
hull = convex_hull(points)
m = len(hull)
perimeter = 0.0
for i in range(m):
perimeter += dist(hull[i], hull[(i+1) % m])
print(perimeter)
solve()Step-by-Step 解説
1外積による回転方向判定
正: 反時計回り、0: 直線上、負: 時計回り。凸包は常に左折り。
正: 反時計回り、0: 直線上、負: 時計回り。凸包は常に左折り。
2下側凸包の構築
左端から右端へスキャン。右折りまたは直線になる点を pop。
左端から右端へスキャン。右折りまたは直線になる点を pop。
3上側凸包
右端から左端へ同様。
右端から左端へ同様。
lower[:-1] + upper[:-1] で重複端点を除く。
4周長計算
隣接頂点間のユークリッド距離の合計。
隣接頂点間のユークリッド距離の合計。
よくあるミス
| ミス | 原因 | 正しい書き方 |
|---|---|---|
cross > 0 で pop | 境界点が残る | <= 0 で pop |
| 上下接合で重複 | lower[-1] == upper[0] | lower[:-1] + upper[:-1] |
| 同一点を含む | cross が 0 で無限ループ | set(points) |
次のステップ
- 発展問題: 凸包の面積（外積の符号付き和 / 2）
- 応用: 半平面交差