java如何在多个点之间找到指定点的最短距离？

Question

我已经输入了点，并找到了它们之间的距离。现在我想找出m点之间的距离最短

import java.awt.Point;
import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;


public class Solution 
{
    public static void main(String[] args) 
    {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int m = in.nextInt();
        int k = in.nextInt();
        Point[] coordinates=new Point[10];
        double dist;
        for(int i = 0; i < m; i++)
        {
            coordinates[i]=new Point(in.nextInt(),in.nextInt());
        }
        for(int i=0;i<m-1;i++)
        {       
            dist=Math.sqrt(((coordinates[i+1].getX()-coordinates[i].getX())*(coordinates[i+1].getX()-coordinates[i].getX()))+((coordinates[i+1].getY()-coordinates[i].getY())*(coordinates[1].getY()-coordinates[0].getY())));
            System.out.println("dist between "+coordinates[i+1].getX()+","+coordinates[i+1].getY()+"and "+coordinates[i].getX()+","+coordinates[i].getY() +" is "+dist);
        }
        in.close();
    }
}

Answer 1

你必须在另一个循环中做一个for循环，以通过每个点的所有点。第一个for循环将通过每个点。第二个循环也将通过所有点，所以在第二个循环中，你将有两个循环的任何可能组合。然后需要计算距离，并检查计算的距离是否小于之前计算的最小距离

最终，你将拥有最小的距离：

• 0.0f表示大小为0或1的点[]
• 点[]的最小距离为2或更大

下面是一些示例代码：

float smallesDistance = 0.0f;
Point[] points = ...;

for(int i = 0; i < points.length; i++) {
    for (int j = 0; j < points.length; j++) {
        if(i != j) { //cant compare on point with itself
            Point a = points[i];
            Point b = points[j];
            float distance = ...; //calculate distance with pythagorean theorem
            if(distance < smallesDistance)
                smallesDistance = distance;
        }
    }
}

如果你需要最大的距离，就用if(distance > smallesDistance)代替if(distance < smallesDistance)

Answer 2

按照for循环的设计方式，它只需检查一个点与紧随其后读取的点。你需要2个for循环来比较每个点和所有其他点

for(int i = 0; i < m - 1; i++)
{
  for (int j = 0; j < m; j++)
  {
     // compare point i with point j and store the smallest here
     // you probably want to discard points where i == j
  }
}

Answer 3

以下是帮助器函数：

1. distance：计算两点之间的距离
2. shortest_pair：返回距离最短的一对

代码如下：

import java.awt.Point;

double distance(Point p1, Point p2)
{
    return Math.sqrt((p1.x - p2.x)*(p1.x - p2.x) + (p1.y - p2.y)*(p1.y - p2.y));
}

int[] shortest_pair(Point[] coordinates)
{
    int m = coordinates.length;
    double shortest_distance = Double.MAX_VALUE;
    int[] shortest_pair = new int[2];
    for (int i = 0; i < m-1; i++)
    {
        for (int j = i+1; j < m; j++)
        {
            double d = distance(coordinates[i], coordinates[j]);
            if (d < shortest_distance)
            {
                shortest_distance = d;
                shortest_pair[0] = i;
                shortest_pair[1] = j;
            }
        }
    }
    return shortest_pair;
}

示例如下：

Random rand = new Random();
rand.setSeed(0);

int m = coordinates.length;
assert m == 10;

for(int i = 0; i < m; i++)
    coordinates[i] = new Point(rand.nextInt(10), rand.nextInt(10));

assert Arrays.equals(shortest_pair(coordinates), new int[] { 2, 7 });