在JAVA中分别用蛮力法和分治法 设置p1 = ( x1 , y1 ) , p2 = ( x2 , y2 ) , ⋯, pn = ( xn , yn )是平面上 n 个点构成的集合 S ,设计算 法找出集合 S 中距离最近的点对。

蛮力法：

import java.util.*;
public class ClosestPair{
    static class Point{
        double x, y;
        public Point(double x, double y){
            this.x = x;
            this.y = y;
        }
    }
    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;
    }
    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);
        }
        double minDist = Double.POSITIVE_INFINITY;
        for(int i = 0; i < n; i++){
            for(int j = i + 1; j < n; j++){
                minDist = Math.min(minDist, dist(points[i], points[j]));
            }
        }
        System.out.printf("%.6f\n", minDist);
    }
}

分治法：

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);
    }
}