import math
def distance(p1, p2):
    return math.sqrt((p1[0]-p2[0])**2+(p1[1]-p2[1])**2)
def closest_pair(points):
    # 按照横坐标排序
    points.sort(key=lambda point:point[0]) 
    def _closest_pair(px, py):
        # 小于等于3个点，不需要分治，直接计算
        if len(px) <= 3:
            min_dist = float('inf')
            best_pair = None 
            for i in range(len(px)):
                for j in range(i+1,len(px)):
                    dist = distance(px[i], px[j])
                    if dist < min_dist:
                        min_dist = dist
                        best_pair = (px[i], px[j])
            return min_dist, best_pair
        # 找到横坐标中间点
        mid = len(px)//2 
        Qx = px[:mid]
        Rx = px[mid:]
        midpoint = px[mid][0]
        # 找到按纵坐标排序的列表里面横坐标小于等于midpoint的点
        Qy = [p for p in py if p[0] <= midpoint]
        Ry = [p for p in py if p[0] > midpoint]
        dl, pair_l = _closest_pair(Qx, Qy)
        dr, pair_r = _closest_pair(Rx, Ry)
        # 比较横坐标中间点左右两边点集内的最小距离
        d = min(dl, dr)
        min_pair = pair_l if dl < dr else pair_r
        #找到横坐标中间点左右d的条带，且是已经按照纵坐标排好序的，可以节省时间复杂度不需要在递归函数里排序
        strip = [p for p in py if abs(p[0]-midpoint) < d]
        for i, p in enumerate(strip):
            #根据鸽笼原理，纵向为2d，横向为d的区域内最多有6个点到p的距离<d
            for j in range(i+1, min(i+8, len(strip))):
                dist = distance(p, strip[j])
                if dist < d:
                    d = dist
                    min_pair = (p, strip[j])
        return d, min_pair
    # 按照纵坐标排序
    py = sorted(points, key=lambda point:point[1])
    return _closest_pair(points, py)

points = [(2, 3), (12, 30), (40, 50), (5, 1), (12, 10), (3, 4)]
print(closest_pair(points)[0])