java实现最近点对问题(附完整源码)

最近点对问题是指在一个平面上给定n个点，找出其中距离最近的两个点。下面是Java实现最近点对问题的示例代码：

import java.util.Arrays;

public class ClosestPair {

    static class Point {
        double x;
        double y;

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

    public static double closestPair(Point[] points) {
        Arrays.sort(points, (a, b) -> Double.compare(a.x, b.x));
        return closestPair(points, 0, points.length - 1);
    }

    private static double closestPair(Point[] points, int left, int right) {
        if (left >= right) {
            return Double.POSITIVE_INFINITY;
        }
        int mid = (left + right) / 2;
        double minLeft = closestPair(points, left, mid);
        double minRight = closestPair(points, mid + 1, right);
        double min = Math.min(minLeft, minRight);
        Point[] strip = new Point[right - left + 1];
        int j = 0;
        for (int i = left; i <= right; i++) {
            if (Math.abs(points[i].x - points[mid].x) < min) {
                strip[j++] = points[i];
            }
        }
        Arrays.sort(strip, 0, j, (a, b) -> Double.compare(a.y, b.y));
        for (int i = 0; i < j; i++) {
            for (int k = i + 1; k < j && strip[k].y - strip[i].y < min; k++) {
                double dist = distance(strip[i], strip[k]);
                if (dist < min) {
                    min = dist;
                }
            }
        }
        return min;
    }

    private static double distance(Point a, Point b) {
        double dx = a.x - b.x;
        double dy = a.y - b.y;
        return Math.sqrt(dx * dx + dy * dy);
    }

    public static void main(String[] args) {
        Point[] points = {new Point(1, 1), new Point(2, 2), new Point(3, 3),
                          new Point(4, 4), new Point(5, 5), new Point(6, 6)};
        double closest = closestPair(points);
        System.out.println("Closest pair distance: " + closest);
    }
}

上述代码使用了分治法，将平面分成左右两部分，分别求出两部分的最近点对距离，然后在中间的条带区域内找到可能更小的距离。最终返回最小的距离。