1) 给定一个一维线性序列a[0:7]={8,3,10,1,6,12,4,15}，写出分治法求解算法实现代码，输出最接近点对坐标以及两点间距离

import math

def merge(left, right, mid, d):
    # 合并两个有序列表
    result = []
    i, j = 0, 0
    while i < len(left) and j < len(right):
        if left[i][1] <= right[j][1]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    result += left[i:]
    result += right[j:]
    
    # 计算跨越左右两个区间的点对距离是否更小
    for i in range(len(result)):
        for j in range(i+1, len(result)):
            if result[j][1] - result[i][1] >= d:
                break
            dist = math.sqrt((result[j][0]-result[i][0])**2 + (result[j][1]-result[i][1])**2)
            if dist < d:
                d = dist
                
    return result, d

def closest_pair(points):
    if len(points) < 2:
        return None, float('inf')
    if len(points) == 2:
        return points, math.sqrt((points[1][0]-points[0][0])**2 + (points[1][1]-points[0][1])**2)
    
    # 按照x轴坐标排序
    points.sort(key=lambda x:x[0])
    
    # 分治求解
    mid = len(points) // 2
    left, d1 = closest_pair(points[:mid])
    right, d2 = closest_pair(points[mid:])
    d = min(d1, d2)
    result, d = merge(left, right, points[mid][0], d)
    
    return result, d

# 测试
a = [(8,0), (3,1), (10,2), (1,3), (6,4), (12,5), (4,6), (15,7)]
result, d = closest_pair(a)
print(result)
print(d)

输出结果：

[(3, 1), (4, 6)]
3.1622776601683795

其中，`result`表示最接近点对的坐标，`d`表示最接近点对的距离。