最近点対
(Geometry/closest_pair.py)

• View this file on GitHub
• Last update: 2021-02-07 13:29:47+09:00

概要

点の集合のうち最も近い点同士 (最近点対) の距離を求める分割統治アルゴリズム。

使い方

closest_pair(points: Sequence[Tuple[float, float]]) -> float
2次元平面上の $N$ 個の点集合 points のうち最も近い点同士 (最近点対) の距離を返す。計算量 $O(N\log N)$

Verified with

• TestCase/AOJ/CGL_5_A.test.py

Code

def merge(ps_l, ps_r):
    """merge the two lists sorted by y-coordinates into one."""
    szl, szr = len(ps_l), len(ps_r)
    ps = []
    il, ir = 0, 0
    for i in range(szl + szr):
        if ir == szr:
            ps.append(ps_l[il])
            il += 1
        elif il == szl:
            ps.append(ps_r[ir])
            ir += 1
        elif ps_l[il][1] < ps_r[ir][1]:
            ps.append(ps_l[il])
            il += 1
        else:
            ps.append(ps_r[ir])
            ir += 1
    return ps


def closest_pair_rec(points):
    """calculate closest pair's distance by divide-and-conquer."""
    INF = 1.0 * 10 ** 9
    size = len(points)
    if size <= 1:
        return INF, points
    mid = size // 2
    x_mid = points[mid][0]
    dist_l, ps_l = closest_pair_rec(points[0:mid])
    dist_r, ps_r = closest_pair_rec(points[mid:size])
    dist = min(dist_l, dist_r)
    ps = merge(ps_l, ps_r)
    qs = []
    for xp, yp in ps:
        if abs(xp - x_mid) >= dist:
            continue
        for xq, yq in reversed(qs):
            dx = xp - xq
            dy = yp - yq
            if dy >= dist:
                break
            dist = min((dx ** 2 + dy ** 2) ** 0.5, dist)
        qs.append((xp, yp))
    return dist, ps


def closest_pair(points):
    dist, _ = closest_pair_rec(sorted(points))
    return dist

Traceback (most recent call last):
  File "/opt/hostedtoolcache/Python/3.12.4/x64/lib/python3.12/site-packages/onlinejudge_verify/documentation/build.py", line 71, in _render_source_code_stat
    bundled_code = language.bundle(stat.path, basedir=basedir, options={'include_paths': [basedir]}).decode()
                   ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/opt/hostedtoolcache/Python/3.12.4/x64/lib/python3.12/site-packages/onlinejudge_verify/languages/python.py", line 96, in bundle
    raise NotImplementedError
NotImplementedError

Back to top page