java - 使用基本函数查找最近的点对

Question

我正在尝试找到最近的一对点，但我的代码就是行不通。我不是这方面的专家，请帮助我。这是我的项目 T_T

我的代码是这样的:

import java.util.Scanner;
public class FindingClosestPair {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);

        System.out.print("Enter the number of points: ");
        int nPoints = input.nextInt();

        System.out.print("Enter "+nPoints+" points: ");
        float [][] points = new float [nPoints][2];
        for(int r=0; r<points.length; r++){
            for(int c=0; c<points[0].length; c++){
                points[r][c] = input.nextFloat(); 
            }
        }

        for(int r=0; r<points.length; r++){
            for(float e : points[r]){
                System.out.print(e+" ");
            }
            System.out.println();
        }

        float p1=0, p2=0, shortestDistance=0, d1=0, d2=0, d=0;
        float x1=0, x2 = 0, x3=0, y1=0, y2 = 0, y3=0;
        float a1=0, a2=0, b1=0, b2=0;

        for(int r1=0; r1<points.length-2; r1++){
            x1 = points[r1][0];
            y1 = points[r1][1];
            for(int r2=r1+1; r2<points.length-1; r2++){
                x2 = points[r2][0];
                y2 = points[r2][1];
                d1 = (float) Math.sqrt((Math.pow(x2-x1, 2))+(Math.pow(y2-y1, 2)));
                for(int r3=r2+1; r3<points.length; r3++){
                    x3 = points[r3][0];
                    y3 = points[r3][1];
                    d2 = (float) Math.sqrt((Math.pow(x3-x1, 2))+(Math.pow(y3-y1, 2)));
                    if(d1<d2){
                        d=d1;
                        a1=x1; b1=y1;
                        a2=x2; b2=y2;
                    }else if(d2<d1){
                        d=d2;
                        a1=x1; b1=y1;
                        a2=x3; b2=y3;
                    }
                }
            }
        }

        System.out.println("The closest two points are ("+a1+","+b1+") and ("+a2+","+b2+")");
    }
}

就是这样。我很糟糕，对吧？ T_T

Answer 1

少一个循环行不行？在浏览器中编写的伪代码:

int clostestPointA = 0;
int clostestPointB = 1;
float closestDist = float.MAX_VALUE;

for(int pointA=0; pointA<points.length-1; pointA++){
    xA = points[pointA][0];
    yA = points[pointA][1];
    for(int pointB=pointA+1; pointB<points.length; pointB++){
        xB = points[pointB][0];
        yB = points[pointB][1];
        d1 = Math.pow(xA-xB, 2) + Math.pow(yA-yB, 2); //dist squared, squareroots are slow and not needed for the comparison
        if(d1 < closestDist){
            //set clostestPointA and clostestPointB
            closestPointA = pointA;
            closestPointB = pointB;
            closestDist = d1;
        }
    }
}