在二维分布中查找两个最近的点

import math

def closest_points(P):
    if len(P) <= 3:
        return brute_force(P)

    mid = len(P) // 2
    Q = P[:mid]
    R = P[mid:]

    q1, q2 = closest_points(Q), closest_points(R)
    d = min(distance(q1), distance(q2))
    strip = [point for point in P if abs(point[0] - P[mid][0]) < d]

    return min(d, closest_strip(strip, d))

def brute_force(P):
    min_distance = math.inf
    min_points = None

    for i in range(len(P)):
        for j in range(i+1, len(P)):
            d = distance(P[i], P[j])
            if d < min_distance:
                min_distance = d
                min_points = (P[i], P[j])

    return min_points

def distance(p1, p2):
    return math.sqrt((p1[0] - p2[0])**2 + (p1[1] - p2[1])**2)

def closest_strip(strip, d):
    min_distance = d
    min_points = None

    for i in range(len(strip)):
        for j in range(i+1, min(i+8, len(strip))):
            d = distance(strip[i], strip[j])
            if d < min_distance:
                min_distance = d
                min_points = (strip[i], strip[j])

    return min_points

# 测试示例
points = [(2, 3), (12, 30), (40, 50), (5, 1), (12, 10), (3, 4)]
closest = closest_points(sorted(points, key=lambda x: x[0]))

print("Closest points:", closest)
print("Distance:", distance(closest[0], closest[1]))