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

以下为Java实现：

import java.util.Arrays;

public class ClosestPair {
    static class Point {
        int x, y;
        Point(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }

    public static void main(String[] args) {
        Point[] points = {new Point(8, 0), new Point(3, 1), new Point(10, 2),
                          new Point(1, 3), new Point(6, 4), new Point(12, 5),
                          new Point(4, 6), new Point(15, 7)};
        Point[] sortedX = Arrays.copyOf(points, points.length);
        Arrays.sort(sortedX, (a, b) -> a.x - b.x);

        Point[] sortedY = Arrays.copyOf(sortedX, sortedX.length);
        Point[] tmp = new Point[sortedX.length];

        System.out.println("最近点对的坐标为：");
        Point[] closest = closestPair(sortedX, sortedY, 0, points.length - 1, tmp);
        System.out.println("(" + closest[0].x + ", " + closest[0].y + ")");
        System.out.println("(" + closest[1].x + ", " + closest[1].y + ")");
        System.out.println("最近距离为：" + dist(closest[0], closest[1]));
    }

    static Point[] closestPair(Point[] sortedX, Point[] sortedY, int left, int right, Point[] tmp) {
        if (left == right) return new Point[]{sortedX[left], sortedY[left]};
        int mid = (left + right) / 2;

        Point[] leftPair = closestPair(sortedX, sortedY, left, mid, tmp);
        Point[] rightPair = closestPair(sortedX, sortedY, mid + 1, right, tmp);
        Point[] closest = dist(leftPair[0], leftPair[1]) < dist(rightPair[0], rightPair[1]) ? leftPair : rightPair;

        int count = 0;
        for (int i = left; i <= right; i++) {
            if (Math.abs(sortedY[i].x - sortedX[mid].x) < dist(closest[0], closest[1])) {
                tmp[count++] = sortedY[i];
            }
        }

        for (int i = 0; i < count; i++) {
            for (int j = i + 1; j < count && tmp[j].y - tmp[i].y < dist(closest[0], closest[1]); j++) {
                double d = dist(tmp[i], tmp[j]);
                if (d < dist(closest[0], closest[1])) {
                    closest[0] = tmp[i];
                    closest[1] = tmp[j];
                }
            }
        }

        return closest;
    }

    static double dist(Point p1, Point p2) {
        return Math.sqrt((p1.x - p2.x) * (p1.x - p2.x) + (p1.y - p2.y) * (p1.y - p2.y));
    }
}

运行结果如下：

最近点对的坐标为：
(6, 4)
(8, 0)
最近距离为：4.472136