Day 050-Q2 | 半平面交差による凸多角形核（Convex Polygon Kernel）

問題

$N$ 辺の多角形（頂点を反時計回りに与える）の 核（Kernel） の面積を求めよ。核とは多角形内部のどの点からも多角形全体が見える点の集合（可視領域の共通部分）である。

核は空集合の場合もある（その場合は 0.000000 を出力）。

制約

$3 \le N \le 10^5$

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

頂点は反時計回りに与えられる

時間制限: 3秒 / 誤差 $10^{-6}$ 以内

入出力例

入力例 1（正方形）

出力例 1

16.000000

入力例 2（六角形）

出力例 2

9.500000

概念図: 半平面交差による核の計算

ヒント（段階的開示）

ヒント1: 方向性

多角形の核 = 各辺の「内側」に対応する半平面すべての共通部分（半平面交差）。凸多角形の場合、核は多角形自身。

ヒント2: アプローチ

各辺 $(P_i, P_{i+1})$ について、多角形内側を向く半平面 $H_i$ を定義（反時計回りなら左側が内側）
半平面を偏角でソートし、同偏角は内側（より厳しい）だけ残す
Deque（両端キュー）で前後を削減しながら交差を計算
残った頂点列の面積を Shoelace 公式で計算

ヒント3: 半平面の表現と交点計算

import math
EPS = 1e-9

# 半平面: 点 p を通り方向 d の左側
def line_intersect(p1, d1, p2, d2):
    denom = d1[0]*d2[1] - d1[1]*d2[0]
    if abs(denom) < EPS: return None
    t = ((p2[0]-p1[0])*d2[1] - (p2[1]-p1[1])*d2[0]) / denom
    return (p1[0]+t*d1[0], p1[1]+t*d1[1])

def on_left(hp_p, hp_d, pt):
    # クロス積 > -EPS なら左側（内側）
    cx = (hp_p[0]+hp_d[0]-hp_p[0])*(pt[1]-hp_p[1]) - (hp_p[1]+hp_d[1]-hp_p[1])*(pt[0]-hp_p[0])
    return cx > -EPS

模範解答 (Python)

import sys, math
from functools import cmp_to_key
input = sys.stdin.readline

EPS = 1e-9

def cross2d(ox, oy, ax, ay, bx, by):
    return (ax-ox)*(by-oy) - (ay-oy)*(bx-ox)

def line_inter(p1, d1, p2, d2):
    denom = d1[0]*d2[1] - d1[1]*d2[0]
    if abs(denom) < EPS: return None
    t = ((p2[0]-p1[0])*d2[1]-(p2[1]-p1[1])*d2[0])/denom
    return (p1[0]+t*d1[0], p1[1]+t*d1[1])

def on_left(p, d, pt):
    return cross2d(p[0],p[1],p[0]+d[0],p[1]+d[1],pt[0],pt[1]) > -EPS

def hp_intersect(hps):
    def cmp(a, b):
        da, db = a[2], b[2]
        if abs(da-db) < EPS:
            v = cross2d(a[0][0],a[0][1],a[0][0]+a[1][0],a[0][1]+a[1][1],b[0][0],b[0][1])
            return -1 if v > 0 else 1
        return -1 if da < db else 1
    hps.sort(key=cmp_to_key(cmp))
    filt = []
    for hp in hps:
        if not filt or abs(hp[2]-filt[-1][2]) > EPS:
            filt.append(hp)
    hps = filt
    n = len(hps)
    if n < 3: return []
    dq = [None]*(2*n); pts = [None]*(2*n)
    head = n; tail = n
    dq[head] = hps[0]; dq[head+1] = hps[1]; tail = head+2
    for i in range(2, n):
        while head+1 < tail:
            pt = line_inter(dq[tail-2][0],dq[tail-2][1],dq[tail-1][0],dq[tail-1][1])
            if pt and not on_left(hps[i][0],hps[i][1],pt): tail -= 1
            else: break
        while head+1 < tail:
            pt = line_inter(dq[head][0],dq[head][1],dq[head+1][0],dq[head+1][1])
            if pt and not on_left(hps[i][0],hps[i][1],pt): head += 1
            else: break
        dq[tail] = hps[i]; tail += 1
    while head+1 < tail:
        pt = line_inter(dq[tail-2][0],dq[tail-2][1],dq[tail-1][0],dq[tail-1][1])
        if pt and not on_left(dq[head][0],dq[head][1],pt): tail -= 1
        else: break
    while head+1 < tail:
        pt = line_inter(dq[head][0],dq[head][1],dq[head+1][0],dq[head+1][1])
        if pt and not on_left(dq[tail-1][0],dq[tail-1][1],pt): head += 1
        else: break
    if tail-head < 3: return []
    res = []
    for i in range(head, tail-1):
        pt = line_inter(dq[i][0],dq[i][1],dq[i+1][0],dq[i+1][1])
        if pt: res.append(pt)
    pt = line_inter(dq[tail-1][0],dq[tail-1][1],dq[head][0],dq[head][1])
    if pt: res.append(pt)
    return res

def polygon_area(pts):
    n = len(pts)
    if n < 3: return 0.0
    area = 0.0
    for i in range(n):
        j = (i+1)%n
        area += pts[i][0]*pts[j][1] - pts[j][0]*pts[i][1]
    return abs(area)/2.0

def solve():
    N = int(input())
    poly = [tuple(map(int, input().split())) for _ in range(N)]
    hps = []
    for i in range(N):
        p = poly[i]; q = poly[(i+1)%N]
        d = (q[0]-p[0], q[1]-p[1])
        ang = math.atan2(d[1], d[0])
        hps.append((p, d, ang))
    kernel = hp_intersect(hps)
    print(f"{polygon_area(kernel):.6f}")

solve()

Step-by-Step 解説

1半平面の定義
辺 $(P_i, P_{i+1})$ の進行方向の左側が多角形の内側（反時計回り前提）。半平面 $H_i$ = 「$P_i$ を通り方向 $P_{i+1}-P_i$ の左側にある点の集合」。

2偏角ソートと同方向フィルタ
全半平面を方向ベクトルの偏角 $\theta = \text{atan2}(d_y, d_x)$ でソート。同偏角（平行な境界線）は内側（より制約の強い）もの一つだけ残す。

3Deque による逐次交差計算
半平面を1つずつ追加。Deque の末端の交点が新半平面の外側なら末端を削除。同様に先端も確認。

4最終整合性チェック
全処理後、先端と末端も互いに確認。3辺未満なら核は空集合（面積 0）。

5面積計算（Shoelace 公式）
残った頂点列 $(x_0,y_0),\ldots,(x_{n-1},y_{n-1})$ の面積 $= \frac{1}{2}|\sum_i (x_i y_{i+1} - x_{i+1} y_i)|$。

計算量

ソート: $O(N \log N)$
Deque 処理: $O(N)$（各半平面は最大1回追加・1回削除）
全体: $O(N \log N)$
空間: $O(N)$

よくあるミス

ミス	原因	正しい書き方
時計回りの頂点を反時計回りとして処理	内外判定が逆になる	入力後に面積符号を確認。負なら逆順にする
EPS の取り扱いミス	境界上の点の判定ミス	`on_left` は `> -EPS`（境界上 OK）
同方向半平面のフィルタ漏れ	平行な半平面を両方残す	偏角差が EPS 未満なら同方向として処理
Deque の頭・尾チェック順序ミス	最終チェックを省略	全 hp 追加後も先端・末端の整合性を確認

次のステップ

発展問題: $N$ 個の半平面交差で囲まれた領域の面積最大化（線形計画の幾何的解法）
関連: 双対変換（点↔直線）により別の問題に帰着する手法
応用: 動的半平面交差（Li Chao Tree との関連）

自己評価

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