Java代码实现最近对问题（分治法） int ClosestPoints (S) / / S 为平面上 n 个点的坐标组成的集合 { 1.if ( n < 2 ) return ∞; 2.m = S 中各点 x 坐标的中位数; 3.构造 S1 和 S2 ,使得 S1 中点的 x 坐标小于 m, S2 中点的 x 坐标大于 m; 4.d1 = ClosestPoints (S1 ) ; d2 = ClosestPoints( S2) ; 5.d = min( d1, d2 ) ; 6 .构造 P1 和 P2 ,使得 P1 是 S1 中点的 x 坐标与 m 的距离小于 d 的点集, P2 是 S2 中点的 x 坐标与 m 的距离小于 d 的点集; 7.将 P1 和 P2 中的点按 y 坐标升序排列; 8.对 P1 中的每一个点 p ,在 P2 中查找与点 p 的 y 坐标小于 d 的点,并求出其中的最 小 距离 d′ ; 9.return min( d, d′ ) ; }

以下是Java代码实现最近对问题的分治算法：

public class ClosestPoints {
    class Point {
        double x, y;

        public Point(double x, double y) {
            this.x = x;
            this.y = y;
        }
    }

    // 计算两点之间的距离
    private double dist(Point p1, Point p2) {
        double dx = p1.x - p2.x;
        double dy = p1.y - p2.y;
        return Math.sqrt(dx * dx + dy * dy);
    }

    // 分治求解最近点对问题
    private double closestPointsRec(Point[] points, int start, int end) {
        if (end - start < 2) { // 如果只有一个点或没有点，则距离为无穷大
            return Double.POSITIVE_INFINITY;
        } else if (end - start == 2) { // 如果只有两个点，则直接计算距离
            return dist(points[start], points[start + 1]);
        }

        // 计算中位数
        int mid = (start + end) / 2;
        double midX = points[mid].x;

        // 分别对左右两个子集递归求解最近点对距离
        double d1 = closestPointsRec(points, start, mid);
        double d2 = closestPointsRec(points, mid, end);
        double d = Math.min(d1, d2);

        // 将距离中位数线距离小于d的点放入集合P中
        List<Point> P = new ArrayList<>();
        for (int i = start; i < end; i++) {
            if (Math.abs(points[i].x - midX) < d) {
                P.add(points[i]);
            }
        }

        // 将集合P中的点按照y坐标升序排序
        Collections.sort(P, (p1, p2) -> Double.compare(p1.y, p2.y));

        // 查找两个子集中的最近点对距离
        for (int i = 0; i < P.size(); i++) {
            for (int j = i + 1; j < P.size() && P.get(j).y - P.get(i).y < d; j++) {
                double dist = dist(P.get(i), P.get(j));
                d = Math.min(d, dist);
            }
        }

        return d;
    }

    // 对外暴露的接口
    public double closestPoints(Point[] points) {
        Arrays.sort(points, (p1, p2) -> Double.compare(p1.x, p2.x));
        return closestPointsRec(points, 0, points.length);
    }
}

其中，Point类表示平面上的点，dist方法计算两个点之间的距离，closestPointsRec方法为递归求解最近点对距离的函数，closestPoints方法为对外暴露的接口。