如何打印分治算法实现的最近点对？代码问题求助

我基于分治（divide et impera）思路实现了寻找n个点中最近点对的程序，目前能正确返回最小距离delta，但无法正确打印对应的最近点对。

初始尝试的问题 #

最初我在bruteForce()方法中将点存入bfList，代码如下：

public double bruteForce(Point[] P, int n) {
    double delta1 = Math.sqrt(Math.pow(FTCPPanel.WIDTH, 2) + Math.pow(FTCPPanel.HEIGHT, 2));
    for (int i = 0; i < n; i++) {
        bfList.add(P[i]);
        
        for (int j = i+1; j < n; j++) {
            double deltam = distance(P[i],P[j]);
            if(deltam < delta1) {
                delta1 = deltam;            
            }
        }
    }
    
    return delta1;
}

这段代码会把数组P中的所有点都加入列表，完全不符合记录最近点对的需求。

修改后的代码及问题 #

于是我修改了bruteForce代码：

double delta1=Math.sqrt(Math.pow(FTCPPanel.WIDTH, 2)+Math.pow(FTCPPanel.HEIGHT, 2));
for(int i=0; i<n;i++) {
    for(int j=i+1;j<n;j++) {
        double deltam=distance(P[i],P[j]);
        if(deltam<delta1) {
            delta1=deltam;  
            bfList.add(P[i]);
            bfList.add(P[j]);
        }
    }
}
return delta1;

同时修改了closestPointsArray方法：

public Point[] closestPointsArray(List<Point> list,List<Point> list1) {
    int size1 = list.size(); //another list with other points that I checked
    int size = list1.size(); //the bruteforce one
    double dist = Double.MAX_VALUE;
    System.out.println("list"+list); //this is just for my output
    Point[]cp=list.toArray(new Point[size1]);
    Point[] l= list1.toArray(new Point[size]);
    Point[]cp1 = new Point[2];
    
    System.out.println("list l"+list1);
    System.out.println("list cp"+list);
    
    for(int i=0;i<size; i=i+2) { //I use this one to can the array and found the closest here in the bruteforce, but something is wrong
            int j=i+1;
            double distij=distance(l[i],l[j]);
            if(distij<=dist) {
                dist=distij;
                cp1[0]=l[i];
                cp1[1]=l[j];
            
        }
    }
    if(list.isEmpty()) {
        return cp1;
    }else {
        double distL=distance(cp1[0],cp1[1]);
        double distCP=distance(cp[0],cp[1]);
        System.out.println("dist L"+distL);
        System.out.println("dist CP"+distCP);
        
        if(distCP<distL) {
            return cp;
        }else {
            return cp1;
        }
    }
}

我原本想用步长为2的循环遍历列表中的点对（0,1）、（2,3）……来找到最近点对，但有时会出现距离为0的错误，而实际两点距离并非0。

问题根源及解决方案 #

问题分析 #

1. bruteForce方法的冗余存储：每次找到更小距离时就往bfList添加点对，导致列表中积累了所有历史上的“候选最近点对”，而非只保留当前最小的那一对。后续遍历这些冗余数据时，可能会拿到旧的点对，甚至出现重复添加同一个点的情况，导致计算出距离为0的错误。
2. closestPointsArray的无效遍历：步长为2的遍历完全没必要，因为我们只需要当前最小的点对，而非所有历史候选对。同时对分治结果的处理没有做有效性校验（比如list的大小是否为2）。

修复后的代码 #

修复bruteForce方法

只保留当前最小的点对，每次找到更小距离时清空列表再添加新点对：

public double bruteForce(Point[] P, int n) {
    double delta1 = Math.sqrt(Math.pow(FTCPPanel.WIDTH, 2) + Math.pow(FTCPPanel.HEIGHT, 2));
    // 先清空列表，避免历史数据干扰
    bfList.clear();
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            double deltam = distance(P[i], P[j]);
            if (deltam < delta1) {
                delta1 = deltam;
                // 找到更小距离，清空列表后添加当前点对
                bfList.clear();
                bfList.add(P[i]);
                bfList.add(P[j]);
            } else if (deltam == delta1) {
                // 可选：如果存在多个距离相同的最近点对，可添加到列表中
                bfList.add(P[i]);
                bfList.add(P[j]);
            }
        }
    }
    return delta1;
}

修复closestPointsArray方法

直接获取列表中的有效点对，无需遍历所有历史数据：

public Point[] closestPointsArray(List<Point> divideList, List<Point> bruteList) {
    // 处理暴力搜索得到的点对
    Point[] brutePair = new Point[2];
    if (!bruteList.isEmpty()) {
        // 取第一个最近点对（如果有多对可扩展逻辑）
        brutePair[0] = bruteList.get(0);
        brutePair[1] = bruteList.get(1);
    } else {
        // 容错：当n<2时返回空数组
        return brutePair;
    }

    // 处理分治得到的点对
    if (divideList.isEmpty()) {
        return brutePair;
    }
    // 确保分治结果是有效的点对（大小为2）
    if (divideList.size() != 2) {
        return brutePair;
    }
    Point[] dividePair = divideList.toArray(new Point[2]);

    // 比较两个点对的距离，返回更小的那个
    double bruteDist = distance(brutePair[0], brutePair[1]);
    double divideDist = distance(dividePair[0], dividePair[1]);

    return divideDist < bruteDist ? dividePair : brutePair;
}

内容的提问来源于stack exchange，提问作者imtrying727