《算法导论》寻找最近点对问题的 Python 实现

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
# -*- coding: utf-8 -*-
# @File  : nearest_dot_pair_final.py
# @Author: FanLu
# @Date  : 2021/5/3

'''
寻找最近点对问题
'''
import math

def get_dist(a:tuple, b:tuple):
    '''
    获取两点之间的欧几里得距离
    :param a: 点 a
    :param b: 点 b
    :return: 两点间的欧几里得距离
    '''
    dist = math.sqrt((a[0] - b[0]) ** 2 + (a[1] - b[1]) ** 2)
    return dist

def brute_get_min(Q:list):
    '''
    暴力求解最小点对问题
    :param Q: 点的全集
    :return: 最近点对，最近点对的距离
    '''
    point_pair = [(0, 0), (float('inf'), float('inf'))] # 初始最近点对为原点和无穷点
    dist_min = float('inf') # 初始最近点对的距离是无穷大
    for i in range(len(Q)):
        a = Q[i]
        for j in range(i + 1, len(Q)):
            b = Q[j]
            dist = get_dist(a, b)
            if dist < dist_min:
                dist_min = dist
                point_pair[0] = a
                point_pair[1] = b
    return [point_pair, dist_min]

def find_dotpair(P:list, X:list, Y:list):
    '''
    找出最近点对
    :param P: 点的全集 Q 的子集
    :param X: P 中的所有点按照 x 坐标排序的结果
    :param Y: P 中的所有点按照 y 坐标排序的结果
    :return: 点对，最短距离
    '''
    n = len(P) # 获取点的总数，这同时是 P.len，X.len 和 Y.len
    # n <= 3 时，直接暴力求解
    if n <= 3:
        point_pair = [(0, 0), (float('inf'), float('inf'))]
        dist_min = float('inf')
        for i in range(n):
            for j in range(i + 1, n):
                if get_dist(P[i], P[j]) < dist_min:
                    point_pair[0] = P[i]
                    point_pair[1] = P[j]
                    dist_min = get_dist(P[i], P[j])
        return [point_pair, dist_min]

    # 求出递归所需的参数
    half = math.ceil(n / 2)
    XL = X[:half]
    XR = X[half:]
    PL = [i for i in P if i in XL]
    PR = [i for i in P if i in XR]
    # 对中间的边界的可能重复的元素进行处理
    while len(PL) != len(XL):
        PL.remove(XL[-1])
    while len(PR) != len(XR):
        PR.remove(XR[0])
    YL = []
    YR = []
    L_len = R_len = 0
    for i in range(0, n):
        if Y[i] in PL:
            YL.append(Y[i])
            L_len += 1
        if Y[i] in PR:
            YR.append(Y[i])
            R_len += 1
    # 对中间的边界的可能重复的元素进行处理
    while len(YL) != len(XL):
        YL.remove(XL[-1])
    while len(YR) != len(XR):
        YR.remove(XR[0])
    # 递归处理
    PL_res = find_dotpair(PL, XL, YL) # 左半部分递归处理结果
    PR_res = find_dotpair(PR, XR, YR) # 右半部分递归处理结果
    point_pair = PL_res[0] if PL_res[1] < PR_res[1] else PR_res[0]
    dist_min = min(PL_res[1], PR_res[1]) # 取左右两个部分中的最小的那一个距离
    # 对中间区域进行处理
    x_mid = (X[half - 1][0] + X[half][0]) / 2 # 中间分割线的 x 坐标
    Y_midarea = [i for i in Y if i[0] >= x_mid - dist_min and i[0] <= x_mid + dist_min] # 中间区域的所有点
    for i in range(len(Y_midarea)):
        for j in range(i + 1, i + 7):
            if j >= len(Y_midarea):
                continue
            if get_dist(Y_midarea[i], Y_midarea[j]) < dist_min:
                point_pair[0] = Y_midarea[i]
                point_pair[1] = Y_midarea[j]
                dist_min = get_dist(Y_midarea[i], Y_midarea[j])
    return [point_pair, dist_min]

import random
def main():
    Q = [(random.randint(0, 256), random.randint(0, 256)) for i in range(128)] # 生成 128 个点
    print(Q)
    # 测试暴力求解法
    brute_res = brute_get_min(Q)
    print('暴力法', brute_res)
    # 测试分治法
    P = Q
    X = sorted(P) # 默认按照 x 坐标排序
    Y = sorted(P, key=lambda p : p[1]) # 按照 Y 坐标排序
    divide_res = find_dotpair(P, X, Y)
    print('分治法', divide_res)

if __name__ == '__main__':
    for i in range(10):
        main()
        print('----------')

这里测试了 10 组数据，输出结果如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
[(84, 15), (221, 232), (186, 143), (221, 1), (52, 100), (129, 188), (50, 213), (12, 29), (30, 201), (208, 160), (15, 248), (185, 115), (254, 239), (210, 102), (139, 79), (204, 135), (140, 0), (235, 163), (197, 176), (137, 104), (144, 159), (220, 180), (51, 227), (211, 139), (134, 59), (225, 219), (100, 198), (81, 91), (134, 177), (139, 12), (142, 17), (88, 1), (251, 165), (12, 210), (166, 241), (28, 142), (224, 139), (109, 113), (109, 166), (193, 68), (230, 17), (210, 88), (119, 168), (206, 248), (78, 241), (66, 40), (66, 55), (178, 83), (199, 179), (238, 226), (170, 211), (237, 135), (18, 231), (169, 90), (159, 196), (103, 115), (230, 141), (94, 89), (136, 174), (29, 231), (148, 34), (1, 0), (209, 40), (220, 229), (173, 246), (212, 150), (191, 60), (221, 96), (79, 188), (41, 246), (123, 116), (210, 139), (146, 211), (97, 48), (186, 116), (245, 21), (244, 223), (205, 102), (85, 28), (66, 24), (249, 210), (49, 78), (224, 253), (115, 20), (104, 60), (250, 131), (203, 41), (130, 129), (44, 215), (137, 123), (72, 205), (198, 166), (63, 248), (236, 237), (93, 247), (98, 241), (143, 165), (176, 246), (15, 167), (231, 194), (197, 248), (39, 77), (107, 239), (107, 149), (53, 188), (188, 9), (112, 29), (243, 152), (94, 209), (232, 251), (193, 30), (127, 15), (235, 55), (180, 93), (128, 104), (167, 194), (202, 113), (3, 170), (209, 22), (159, 80), (26, 196), (21, 62), (191, 236), (227, 121), (136, 223), (21, 111), (108, 192), (148, 207)]
暴力法 [[(211, 139), (210, 139)], 1.0]
分治法 [[(211, 139), (210, 139)], 1.0]
----------
[(116, 20), (172, 213), (181, 186), (181, 145), (106, 120), (249, 125), (98, 143), (114, 201), (50, 47), (183, 122), (160, 253), (236, 87), (40, 125), (180, 111), (202, 183), (210, 57), (118, 103), (162, 177), (78, 57), (248, 77), (184, 43), (165, 193), (39, 135), (21, 237), (99, 36), (232, 54), (220, 219), (175, 17), (151, 92), (189, 195), (249, 7), (126, 129), (153, 216), (19, 198), (48, 205), (228, 181), (190, 200), (39, 121), (54, 167), (130, 200), (24, 121), (4, 106), (118, 42), (104, 16), (43, 3), (242, 251), (91, 47), (142, 103), (62, 224), (123, 195), (225, 177), (166, 238), (105, 176), (144, 174), (163, 199), (43, 219), (229, 96), (131, 239), (113, 129), (32, 103), (163, 42), (87, 0), (184, 130), (79, 87), (134, 208), (75, 187), (3, 53), (140, 25), (139, 77), (8, 2), (198, 148), (71, 225), (235, 48), (27, 112), (217, 74), (46, 45), (117, 20), (199, 125), (14, 253), (169, 208), (91, 62), (138, 115), (36, 89), (13, 61), (23, 84), (141, 82), (101, 188), (189, 12), (10, 17), (185, 89), (142, 181), (92, 255), (139, 60), (230, 167), (72, 239), (117, 49), (233, 45), (210, 212), (111, 9), (188, 159), (214, 22), (111, 202), (95, 254), (99, 148), (36, 238), (240, 13), (138, 164), (98, 229), (55, 101), (254, 128), (15, 64), (189, 205), (142, 15), (62, 24), (135, 65), (117, 64), (112, 120), (72, 197), (252, 129), (210, 5), (105, 11), (210, 64), (71, 39), (14, 16), (157, 150), (229, 132), (41, 180), (193, 121)]
暴力法 [[(116, 20), (117, 20)], 1.0]
分治法 [[(116, 20), (117, 20)], 1.0]
----------
[(148, 202), (195, 27), (64, 65), (137, 57), (76, 27), (255, 26), (67, 255), (4, 39), (213, 212), (109, 51), (125, 149), (96, 102), (188, 191), (28, 104), (36, 202), (193, 210), (35, 160), (160, 200), (26, 2), (17, 127), (67, 105), (137, 74), (244, 176), (87, 106), (195, 141), (253, 233), (247, 9), (252, 239), (160, 194), (145, 82), (197, 229), (78, 199), (90, 122), (160, 194), (93, 80), (111, 1), (154, 251), (199, 233), (188, 34), (108, 144), (75, 70), (233, 98), (203, 6), (256, 56), (84, 90), (243, 224), (224, 249), (129, 98), (110, 102), (93, 144), (159, 247), (5, 60), (221, 175), (256, 58), (93, 56), (230, 100), (145, 97), (110, 114), (21, 84), (143, 33), (124, 41), (88, 68), (208, 117), (54, 78), (241, 129), (247, 92), (75, 159), (135, 219), (11, 159), (196, 171), (90, 197), (180, 256), (184, 207), (118, 158), (232, 184), (244, 105), (95, 169), (121, 236), (215, 109), (112, 89), (172, 126), (72, 153), (84, 112), (204, 121), (17, 23), (118, 152), (206, 84), (95, 145), (161, 98), (123, 210), (136, 11), (232, 77), (35, 34), (209, 203), (111, 225), (207, 33), (214, 174), (170, 71), (213, 139), (198, 118), (16, 181), (181, 157), (44, 239), (184, 61), (85, 150), (252, 16), (202, 43), (5, 250), (79, 170), (57, 126), (235, 174), (57, 40), (175, 123), (231, 130), (57, 106), (136, 187), (148, 89), (68, 57), (48, 200), (95, 122), (248, 18), (127, 171), (14, 120), (93, 205), (133, 35), (8, 254), (183, 209), (95, 153)]
暴力法 [[(160, 194), (160, 194)], 0.0]
分治法 [[(160, 194), (160, 194)], 0.0]
----------
[(182, 36), (205, 46), (56, 106), (246, 173), (255, 177), (174, 103), (231, 97), (143, 30), (166, 90), (145, 212), (15, 196), (249, 224), (192, 5), (73, 252), (23, 151), (123, 182), (110, 87), (179, 211), (143, 61), (168, 30), (228, 213), (89, 17), (241, 87), (163, 254), (242, 44), (204, 110), (185, 5), (152, 65), (41, 244), (126, 254), (104, 114), (128, 65), (46, 102), (154, 188), (111, 72), (94, 29), (117, 6), (234, 200), (105, 243), (96, 190), (15, 85), (74, 27), (80, 106), (34, 197), (217, 44), (144, 180), (114, 155), (67, 122), (31, 146), (171, 87), (78, 147), (242, 231), (103, 130), (212, 59), (23, 183), (134, 157), (110, 113), (192, 120), (11, 131), (186, 64), (210, 243), (119, 125), (165, 56), (158, 145), (154, 216), (47, 2), (95, 207), (246, 202), (181, 58), (214, 56), (22, 5), (19, 65), (173, 85), (215, 16), (47, 129), (32, 217), (0, 119), (118, 48), (180, 208), (55, 122), (62, 185), (26, 232), (99, 223), (73, 170), (141, 41), (222, 153), (180, 91), (42, 251), (45, 156), (20, 117), (73, 233), (65, 148), (34, 43), (197, 69), (192, 69), (82, 245), (98, 66), (4, 136), (247, 191), (143, 197), (178, 67), (3, 91), (251, 217), (217, 45), (175, 105), (187, 47), (12, 142), (64, 74), (150, 248), (228, 112), (225, 145), (166, 191), (161, 129), (190, 41), (124, 1), (207, 16), (9, 253), (147, 88), (75, 191), (76, 54), (128, 0), (237, 30), (71, 46), (150, 17), (147, 219), (68, 194), (21, 165), (149, 29)]
暴力法 [[(217, 44), (217, 45)], 1.0]
分治法 [[(217, 44), (217, 45)], 1.0]
----------
[(85, 218), (31, 202), (218, 246), (175, 131), (170, 125), (155, 8), (137, 165), (193, 179), (232, 251), (17, 111), (227, 28), (235, 34), (150, 8), (49, 176), (40, 88), (129, 34), (20, 167), (1, 100), (17, 86), (112, 176), (235, 116), (82, 91), (248, 230), (86, 48), (53, 194), (133, 165), (13, 39), (7, 60), (61, 62), (190, 112), (194, 117), (34, 118), (219, 193), (125, 247), (146, 72), (107, 23), (127, 168), (53, 59), (218, 18), (94, 28), (135, 120), (119, 251), (119, 142), (116, 152), (10, 31), (169, 27), (23, 124), (222, 92), (252, 97), (60, 80), (10, 80), (107, 197), (198, 151), (49, 48), (17, 211), (248, 52), (248, 11), (140, 167), (26, 223), (171, 153), (153, 197), (50, 241), (158, 47), (13, 163), (225, 135), (209, 136), (102, 241), (214, 63), (233, 130), (24, 157), (12, 195), (13, 222), (233, 5), (17, 118), (48, 206), (22, 140), (72, 71), (169, 131), (18, 250), (181, 227), (73, 193), (162, 16), (135, 235), (139, 72), (44, 130), (18, 212), (130, 97), (211, 40), (222, 171), (75, 50), (62, 70), (122, 119), (7, 22), (81, 161), (96, 206), (223, 100), (1, 128), (202, 109), (215, 232), (190, 0), (37, 181), (127, 185), (32, 161), (70, 239), (239, 125), (35, 30), (155, 115), (163, 245), (1, 154), (3, 63), (48, 89), (10, 18), (149, 151), (196, 182), (76, 222), (162, 115), (147, 1), (98, 132), (88, 129), (134, 215), (207, 90), (222, 57), (121, 145), (255, 33), (117, 234), (153, 213), (8, 173), (50, 29)]
暴力法 [[(17, 211), (18, 212)], 1.4142135623730951]
分治法 [[(17, 211), (18, 212)], 1.4142135623730951]
----------
[(115, 114), (216, 172), (144, 254), (138, 198), (76, 60), (142, 57), (129, 140), (151, 12), (140, 166), (91, 28), (252, 189), (159, 84), (122, 29), (243, 163), (200, 47), (76, 142), (221, 233), (219, 200), (199, 81), (142, 49), (2, 6), (71, 164), (17, 227), (224, 181), (158, 119), (183, 36), (113, 103), (220, 107), (26, 47), (221, 106), (167, 247), (251, 173), (245, 70), (70, 252), (44, 173), (251, 191), (169, 147), (231, 5), (95, 8), (185, 224), (209, 26), (189, 124), (154, 180), (126, 83), (86, 236), (218, 13), (153, 183), (134, 129), (122, 127), (254, 106), (156, 209), (78, 57), (167, 70), (99, 222), (201, 178), (5, 182), (98, 198), (211, 65), (143, 139), (213, 209), (63, 221), (201, 164), (210, 17), (203, 43), (124, 199), (248, 202), (34, 37), (11, 66), (28, 49), (81, 25), (256, 204), (128, 29), (171, 227), (38, 88), (223, 240), (38, 13), (17, 253), (45, 110), (72, 96), (93, 38), (195, 137), (245, 108), (59, 163), (65, 150), (103, 16), (35, 181), (14, 101), (216, 13), (224, 144), (177, 140), (242, 158), (16, 23), (46, 192), (149, 120), (203, 220), (191, 183), (131, 28), (251, 173), (114, 81), (180, 94), (113, 234), (4, 47), (107, 220), (67, 100), (226, 114), (0, 39), (44, 88), (157, 144), (12, 173), (48, 40), (254, 199), (110, 180), (200, 27), (70, 202), (43, 24), (248, 166), (25, 26), (34, 72), (249, 1), (150, 22), (210, 240), (40, 206), (49, 232), (47, 171), (191, 140), (237, 118), (20, 227), (198, 140)]
暴力法 [[(251, 173), (251, 173)], 0.0]
分治法 [[(251, 173), (251, 173)], 0.0]
----------
[(15, 124), (69, 248), (93, 25), (188, 178), (142, 34), (217, 240), (90, 133), (35, 120), (189, 57), (186, 11), (138, 66), (170, 252), (43, 115), (186, 106), (44, 123), (150, 212), (78, 1), (215, 126), (112, 40), (235, 210), (74, 151), (169, 179), (192, 71), (147, 69), (220, 137), (43, 62), (42, 22), (222, 0), (183, 132), (82, 83), (87, 7), (141, 140), (212, 104), (28, 55), (108, 11), (31, 138), (225, 167), (169, 249), (134, 19), (235, 238), (228, 51), (101, 53), (4, 226), (195, 87), (57, 142), (11, 34), (50, 250), (172, 58), (101, 118), (198, 165), (214, 95), (60, 99), (90, 55), (115, 63), (75, 155), (49, 24), (38, 248), (223, 49), (70, 92), (118, 65), (103, 67), (107, 22), (114, 129), (254, 29), (17, 174), (72, 123), (59, 16), (76, 41), (157, 76), (25, 74), (40, 188), (244, 70), (160, 184), (234, 15), (80, 202), (15, 117), (0, 47), (158, 140), (77, 187), (61, 47), (149, 35), (154, 184), (64, 142), (213, 116), (74, 213), (238, 34), (87, 117), (110, 87), (218, 54), (18, 77), (196, 145), (187, 249), (246, 235), (89, 218), (98, 229), (149, 198), (26, 105), (106, 102), (33, 142), (240, 204), (177, 154), (201, 163), (188, 126), (173, 67), (255, 34), (83, 58), (53, 236), (253, 133), (48, 8), (87, 157), (151, 98), (80, 120), (91, 175), (33, 8), (100, 233), (193, 148), (16, 159), (114, 33), (27, 240), (250, 46), (22, 251), (235, 81), (52, 4), (15, 60), (99, 69), (30, 216), (101, 131), (246, 144)]
暴力法 [[(170, 252), (169, 249)], 3.1622776601683795]
分治法 [[(170, 252), (169, 249)], 3.1622776601683795]
----------
[(75, 244), (134, 234), (160, 37), (110, 192), (150, 247), (39, 1), (100, 162), (87, 102), (180, 24), (235, 93), (57, 198), (56, 0), (229, 85), (142, 23), (14, 115), (201, 163), (231, 237), (168, 102), (21, 225), (162, 195), (255, 168), (193, 57), (180, 94), (32, 123), (112, 116), (248, 130), (245, 75), (78, 20), (151, 240), (82, 219), (52, 218), (77, 127), (201, 11), (25, 81), (236, 251), (25, 11), (129, 68), (64, 203), (205, 113), (254, 71), (171, 182), (208, 4), (225, 120), (95, 4), (218, 224), (172, 203), (84, 33), (62, 51), (232, 183), (42, 189), (54, 184), (183, 236), (213, 96), (241, 224), (60, 107), (233, 173), (164, 30), (106, 15), (140, 110), (171, 79), (19, 171), (60, 12), (108, 239), (181, 29), (28, 236), (70, 150), (242, 95), (209, 242), (27, 28), (88, 250), (129, 162), (191, 80), (140, 77), (50, 116), (28, 130), (86, 60), (12, 84), (51, 197), (68, 200), (239, 211), (143, 22), (97, 224), (221, 46), (89, 117), (201, 117), (28, 85), (205, 135), (156, 247), (11, 46), (185, 86), (135, 200), (231, 249), (14, 168), (1, 236), (16, 242), (168, 34), (105, 179), (173, 137), (222, 163), (252, 188), (228, 166), (170, 40), (240, 197), (237, 20), (116, 212), (160, 137), (172, 40), (220, 202), (125, 113), (236, 224), (85, 178), (220, 16), (103, 147), (195, 51), (235, 125), (241, 237), (5, 49), (153, 42), (56, 217), (152, 74), (179, 63), (91, 175), (107, 205), (244, 139), (78, 235), (208, 5), (134, 243), (141, 124)]
暴力法 [[(208, 4), (208, 5)], 1.0]
分治法 [[(208, 4), (208, 5)], 1.0]
----------
[(151, 44), (2, 146), (199, 205), (122, 167), (133, 110), (160, 225), (100, 199), (242, 251), (58, 62), (211, 61), (100, 94), (140, 240), (197, 196), (237, 15), (167, 222), (194, 6), (237, 14), (3, 138), (223, 7), (245, 222), (201, 112), (252, 103), (238, 81), (63, 147), (148, 123), (172, 121), (156, 51), (249, 251), (80, 23), (227, 115), (228, 209), (198, 118), (187, 25), (38, 167), (205, 21), (238, 145), (50, 35), (53, 123), (230, 146), (199, 145), (195, 80), (12, 173), (8, 77), (40, 89), (2, 116), (206, 174), (177, 48), (134, 36), (254, 88), (176, 183), (97, 171), (85, 172), (229, 139), (256, 214), (132, 91), (15, 66), (81, 246), (203, 224), (133, 72), (9, 83), (178, 229), (238, 248), (29, 217), (104, 155), (41, 213), (73, 64), (42, 43), (220, 255), (103, 138), (83, 105), (82, 58), (221, 41), (130, 228), (77, 50), (169, 100), (18, 97), (68, 162), (239, 194), (112, 16), (216, 236), (210, 0), (107, 159), (148, 179), (59, 125), (42, 246), (233, 202), (78, 50), (18, 31), (21, 207), (166, 29), (253, 103), (10, 249), (41, 173), (4, 67), (173, 27), (250, 33), (212, 37), (242, 123), (194, 124), (122, 85), (117, 77), (229, 125), (217, 228), (228, 17), (110, 195), (171, 150), (166, 188), (75, 21), (47, 43), (254, 184), (248, 107), (36, 83), (35, 183), (77, 114), (183, 26), (47, 92), (242, 131), (112, 119), (69, 68), (29, 71), (134, 14), (34, 166), (241, 6), (77, 93), (212, 234), (198, 95), (81, 101), (37, 104)]
暴力法 [[(237, 15), (237, 14)], 1.0]
分治法 [[(252, 103), (253, 103)], 1.0]
----------
[(53, 10), (250, 83), (213, 218), (55, 207), (97, 129), (164, 249), (164, 104), (206, 136), (197, 40), (11, 156), (105, 163), (34, 229), (107, 240), (118, 168), (163, 171), (36, 209), (205, 154), (235, 172), (73, 219), (18, 142), (66, 154), (73, 241), (109, 56), (236, 8), (27, 68), (149, 65), (249, 110), (69, 243), (158, 164), (192, 217), (147, 196), (167, 84), (165, 2), (141, 243), (164, 110), (102, 195), (87, 64), (0, 102), (224, 135), (217, 32), (234, 227), (29, 149), (48, 67), (140, 236), (174, 174), (256, 52), (63, 112), (15, 159), (178, 33), (198, 119), (130, 70), (24, 91), (26, 74), (21, 46), (116, 202), (199, 14), (10, 180), (59, 73), (236, 63), (195, 82), (180, 216), (46, 229), (4, 201), (44, 151), (135, 96), (118, 17), (201, 53), (161, 190), (156, 173), (153, 194), (30, 227), (203, 14), (100, 157), (46, 93), (193, 247), (91, 139), (9, 203), (32, 92), (200, 183), (98, 130), (71, 102), (66, 56), (173, 202), (192, 158), (198, 105), (191, 96), (161, 65), (41, 52), (5, 116), (129, 222), (167, 163), (256, 65), (40, 234), (180, 130), (162, 250), (250, 148), (219, 245), (146, 133), (111, 65), (256, 149), (91, 100), (206, 170), (100, 226), (208, 96), (236, 222), (211, 214), (239, 23), (158, 194), (236, 70), (116, 174), (210, 59), (208, 197), (15, 182), (2, 119), (227, 125), (36, 202), (8, 252), (82, 226), (93, 107), (194, 247), (64, 200), (141, 197), (213, 47), (82, 166), (125, 146), (35, 120), (57, 174), (8, 197)]
暴力法 [[(193, 247), (194, 247)], 1.0]
分治法 [[(193, 247), (194, 247)], 1.0]
----------

说明

关于这个算法，《算法导论》原书中并没有伪码来参考。但是根据书中的详细的描述，写出算法其实是可以的。只是，这其中有一些坑，或者说需要注意的点，需要详细记述一下。如下。

注意点一

寻找一条垂直线 $l$，它把点集 $P$ 对分为满足下列条件的两个集合 $P_L$ 和 $P_R$：使得 $|P_L| = \left \lceil |P| / 2 \right \rceil, \; |P_R| = \left \lfloor |P| / 2 \right \rfloor$，$P_L$ 中的点都在直线 $l$ 上或 $l$ 的左侧，$P_R$ 中的所有点都在直线 $l$ 上或 $l$ 的右侧。

这里划分时，要注意向上和向下取整的问题。另外，在划分时，我使用了这样的代码

1
2
PL = [i for i in P if i in XL]
PR = [i for i in P if i in XR]

其实这两行代码执行后产生的 $P_L$ 和 $P_R$ 是有问题的。问题就出在如果 $X_L$ 和 $X_R$ 中有重复的元素，那么，$|P_L|$ 或者 $P_R$ 的值可能会大于 $X_L$ 或者 $X_R$ 的值。显然，这样是有问题的。所以我们需要对 $P_L$ 和 $P_R$ 进行一些处理

1
2
3
4
5
# 对中间的边界的可能重复的元素进行处理
while len(PL) != len(XL):
    PL.remove(XL[-1])
while len(PR) != len(XR):
    PR.remove(XR[0])

这里的 XL[-1] 和 XR[0] 的值其实是相等的，而且，如果 PL 或者 PR 中出现了多余的元素，那么，多余的元素也一定是这个中间边界的值。

注意点二

对于 $Y^{'}$ 的处理。具体就是，对于 $Y^{'}$ 中的每一个点 $p$，我们只需要考虑紧随 $p$ 后的 7 个点。

我之前还因为中间的分割线 $l$ 上的重复点问题而异或，重复点的话，两个不是应该算成一个吗？所以为什么不是检查 5 个点呢？后来在解决注意点一的时候想明白了，重复的点是要慎重考虑的，是不能够把两个点算作一个的。

后记

本算法是严格参照《算法导论》原书的描述来实现的。具体过程和算法的正确性的证明请阅读《算法导论》相关章节。

另外，关于分治法的函数的参数问题，我认为，如果要像我一样，在代码中有去重的这一步操作的话，那么，参数 P 是可以省去的。我认为这个参数 P 是多余的。但是为了和书上的描述保持一致，这里就没有去掉这个参数。