java设 p1 = ( x1 , y1 ) , p2 = ( x2 , y2 ) , ⋯, pn = ( xn , yn )是平面上 n 个点构成的集合 S ,设计算 法找出集合 S 中距离最近的点对。

这个问题可以用分治法解决，其时间复杂度为 O(nlogn)。

具体实现步骤如下：

1. 将点按照 x 坐标排序，若 x 坐标相同，则按照 y 坐标排序。

2. 将点集 S 分成左右两部分，分别递归求解左右两部分的最小距离。

3. 对于左右两部分中的任意一对点，其距离最小值必然小于等于 minDist，因此只需要考虑距离分界线左右两侧距离小于 minDist 的点对。

4. 将距离分界线左右两侧的点按照 y 坐标排序，然后以每个点为中心向上下各扫描 7 个点，共 15 个点。注意到只需要考虑距离分界线距离小于 minDist 的点，因此可以用一个指针遍历每个点扫描的范围。

5. 在扫描过程中，使用一个桶存储距离小于 minDist 的点，每次扫描到一个点时，只需要检查其前后各 7 个点是否距离小于 minDist，若满足条件，则加入桶中。

6. 扫描完成后，在桶中找出距离最小的点对，更新 minDist 和对应的点对坐标。

7. 最后返回左右两部分中距离最小的点对。

具体实现可以参考以下 Java 代码：

import java.util.*;

public class ClosestPair {
    static class Point implements Comparable<Point> {
        double x, y;

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

        public int compareTo(Point o) {
            if (x < o.x) return -1;
            if (x > o.x) return 1;
            if (y < o.y) return -1;
            if (y > o.y) return 1;
            return 0;
        }
    }

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

    static double bruteForce(Point[] points, int l, int r) {
        double minDist = Double.POSITIVE_INFINITY;
        for (int i = l; i <= r; i++) {
            for (int j = i + 1; j <= r; j++) {
                minDist = Math.min(minDist, dist(points[i], points[j]));
            }
        }
        return minDist;
    }

    static double closestPair(Point[] points, int l, int r) {
        if (r - l + 1 <= 3) {
            return bruteForce(points, l, r);
        }
        int mid = (l + r) / 2;
        double minDistLeft = closestPair(points, l, mid);
        double minDistRight = closestPair(points, mid + 1, r);
        double minDist = Math.min(minDistLeft, minDistRight);
        List<Point> strip = new ArrayList<>();
        for (int i = l; i <= r; i++) {
            if (Math.abs(points[i].x - points[mid].x) < minDist) {
                strip.add(points[i]);
            }
        }
        Collections.sort(strip, (a, b) -> Double.compare(a.y, b.y));
        int n = strip.size();
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n && strip.get(j).y - strip.get(i).y < minDist; j++) {
                double d = dist(strip.get(i), strip.get(j));
                if (d < minDist) {
                    minDist = d;
                }
            }
        }
        return minDist;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        Point[] points = new Point[n];
        for (int i = 0; i < n; i++) {
            double x = scanner.nextDouble();
            double y = scanner.nextDouble();
            points[i] = new Point(x, y);
        }
        Arrays.sort(points);
        double minDist = closestPair(points, 0, n - 1);
        System.out.printf("%.6f\n", minDist);
    }
}