Day 088-Q5 — Bentley-Ottmann法（線分交差検出・スイープライン）

問題

平面上に $N$ 本の線分が与えられる。すべての交点を重複なく列挙せよ。入力は一般の位置（垂直線分なし、3線分以上の同時交差なし、重なりなし）と仮定してよい。

入出力例

2
0 0 4 4
0 4 4 0

1
2.000000 2.000000

概念図: スイープラインとアクティブ集合の隣接ペアのみ判定

ヒント

events = []
for i, (p1, p2) in enumerate(segs):
    heapq.heappush(events, (p1[0], p1[1], 0, i, -1))  # start
    heapq.heappush(events, (p2[0], p2[1], 2, i, -1))  # end
status = []  # y順に並んだアクティブな線分

模範解答

import sys
import heapq

def seg_y_at_x(p1, p2, x):
    x1, y1 = p1
    x2, y2 = p2
    if x2 == x1:
        return y1
    t = (x - x1) / (x2 - x1)
    return y1 + t * (y2 - y1)

def segments_intersect(p1, p2, p3, p4):
    x1, y1 = p1; x2, y2 = p2; x3, y3 = p3; x4, y4 = p4
    d1x, d1y = x2 - x1, y2 - y1
    d2x, d2y = x4 - x3, y4 - y3
    denom = d1x * d2y - d1y * d2x
    if denom == 0:
        return None
    t = ((x3 - x1) * d2y - (y3 - y1) * d2x) / denom
    u = ((x3 - x1) * d1y - (y3 - y1) * d1x) / denom
    if 0 <= t <= 1 and 0 <= u <= 1:
        return (x1 + t * d1x, y1 + t * d1y)
    return None

def solve():
    data = sys.stdin.read().split()
    idx = 0
    n = int(data[idx]); idx += 1
    segs = []
    for _ in range(n):
        x1, y1, x2, y2 = (int(data[idx + k]) for k in range(4))
        idx += 4
        if (x1, y1) > (x2, y2):
            x1, y1, x2, y2 = x2, y2, x1, y1
        segs.append(((x1, y1), (x2, y2)))

    events = []
    for i, (p1, p2) in enumerate(segs):
        heapq.heappush(events, (p1[0], p1[1], 0, i, -1))
        heapq.heappush(events, (p2[0], p2[1], 2, i, -1))

    status = []
    results = []
    seen = set()

    def try_pair(i, j, cur_x):
        if i is None or j is None or i == j:
            return
        pt = segments_intersect(*segs[i], *segs[j])
        if pt and pt[0] >= cur_x - 1e-9:
            heapq.heappush(events, (pt[0], pt[1], 1, i, j))

    while events:
        x, y, typ, i, j = heapq.heappop(events)
        if typ == 0:
            p1, p2 = segs[i]
            yv = seg_y_at_x(p1, p2, x)
            pos = 0
            while pos < len(status) and seg_y_at_x(*segs[status[pos]], x) < yv:
                pos += 1
            status.insert(pos, i)
            if pos > 0:
                try_pair(status[pos - 1], i, x)
            if pos < len(status) - 1:
                try_pair(i, status[pos + 1], x)
        elif typ == 2:
            pos = status.index(i)
            above = status[pos - 1] if pos > 0 else None
            below = status[pos + 1] if pos < len(status) - 1 else None
            status.pop(pos)
            try_pair(above, below, x)
        else:
            key = (round(x, 6), round(y, 6), min(i, j), max(i, j))
            if key in seen:
                continue
            seen.add(key)
            results.append((x, y))
            if i in status and j in status:
                pi, pj = status.index(i), status.index(j)
                if pi > pj:
                    pi, pj = pj, pi
                status[pi], status[pj] = status[pj], status[pi]
                if pi > 0:
                    try_pair(status[pi - 1], status[pi], x)
                if pj < len(status) - 1:
                    try_pair(status[pj], status[pj + 1], x)

    results.sort()
    out = [str(len(results))]
    for px, py in results:
        out.append(f"{px:.6f} {py:.6f}")
    print('\n'.join(out))

solve()

計算量: 理論上は平衡BSTでアクティブ集合を管理すれば $O((N+K)\log N)$。本解答はリスト管理のため $O(N(N+K))$ だが $N\le300$ では十分高速。

Step-by-Step 解説

Step 1: イベントの種類と順序

各線分は開始・終了イベントを持ち、交差が検出されるたびに交差イベントを動的に追加。優先度付きキューで $x$ 昇順に処理する。

Step 2: アクティブ集合の維持

現在の $x$ における各線分の $y$ 座標でソートされた順序を保持し、開始時に挿入、終了時に削除する。

Step 3: 交差判定は隣接ペアのみでよい

2線分が交差する直前にはアクティブ集合上で必ず隣接する瞬間がある。挿入・削除・交差の直後に新しく隣接した組だけを調べれば全交差を漏れなく検出できる。

Step 4: 交差イベントの処理

交差が発生した時点で順序を入れ替え、新しく隣接したペアを再度判定する。seen 集合で重複除去する。

よくあるミス

次のステップ

• 発展問題: 垂直線分・共有端点・同時交差など退化ケースへの対応
• 高速化: アクティブ集合を平衡BSTで管理し真の $O((N+K)\log N)$ を達成

自己評価