计算两点之间的最短距离

计算两点之间的最短距离

题⽬链接:

题⽬⼤意:

给定N个点的坐标,找出距离最短的两个点的序号.如果最短距离相同,输出序号最⼩的⼀组.

题⽬要求输出三种不同计算⽅式下的最短距离序号:

欧⼏⾥得距离:Math.sqrt(|x2-x1|2+|y2-y1|2)

曼哈顿距离:|x2-x1|+|y2-y1|

棋盘距离:Math.max(|x2-x1|,|y2-y1|)

因为N的个数是5000个,可以直接双重循环取得最⼩距离. 单纯的理解⼀下三种距离.

Accept代码:

import java.io.BufferedReader;

import java.io.IOException;

import java.io.InputStreamReader;

import java.util.ArrayList;

import java.util.List;

import java.util.StringTokenizer;

public class source {

public static void main(String[] args) throws IOException {

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

StringTokenizer st = new StringTokenizer(br.readLine());

int N = Integer.parseInt(st.nextToken());

int[][] points = new int[N+1][2];

for(int i = 1;i<=N;i++){

st = new StringTokenizer(br.readLine());

points[i] = new int[]{Integer.parseInt(st.nextToken()),Integer.parseInt(st.nextToken())};

}

List result = getEuclidPosition(points);

for(int[] ans:result){

System.out.println(ans[0]+" "+ans[1]);

}

}

private static List getEuclidPosition(int[][] points){

double minEuclidDistance = Integer.MAX_VALUE;

int[] euclidPosition = new int[2];

double minCityDistance = Integer.MAX_VALUE;

int[] cityPosition = new int[2];

double minChessDistance = Integer.MAX_VALUE;

int[] chessPosition = new int[2];

CalcMinPoint calcMinPointEuclid;

CalcMinPoint calcMinPointCity;

CalcMinPoint calcMinPointChess;

for(int i = 1;i

for(int j = 1;j

if(i == j){

continue;

}

double euclidDistance = getEuclidDistance(points[i],points[j]);

double cityDistance = getCityDistance(points[i],points[j]);

double chessDistance = getChessDistance(points[i],points[j]);

calcMinPointEuclid = new CalcMinPoint(minEuclidDistance, euclidPosition, i, j, euclidDistance).invoke();

minEuclidDistance = calcMinPointEuclid.getMinEuclidDistance();

euclidPosition = calcMinPointEuclid.getEuclidPosition();

calcMinPointCity = new CalcMinPoint(minCityDistance, cityPosition, i, j, cityDistance).invoke();

minCityDistance = calcMinPointCity.getMinEuclidDistance();

cityPosition = calcMinPointCity.getEuclidPosition();

calcMinPointChess = new CalcMinPoint(minChessDistance, chessPosition, i, j, chessDistance).invoke();

minChessDistance = calcMinPointChess.getMinEuclidDistance();

chessPosition = calcMinPointChess.getEuclidPosition();

}

}

List result = new ArrayList();

result.add(euclidPosition);

result.add(cityPosition);

result.add(chessPosition);

return result;

}

private static double getChessDistance(int[] point, int[] point1) {

return Math.max(Math.abs(point[0]-point1[0]),Math.abs(point[1]-point1[1]));

}

private static double getCityDistance(int[] point, int[] point1) {

return Math.abs(point[0]-point1[0])+Math.abs(point[1]-point1[1]);

}

private static double getEuclidDistance(int[] p1, int[] p2){return Math.pow(p1[0]-p2[0],2)+Math.pow(p1[1]-p2[1],2);

}

private static class CalcMinPoint {

private double minEuclidDistance;

private int[] euclidPosition;

private int i;

private int j;

private double euclidDistance;

public CalcMinPoint(double minEuclidDistance, int[] euclidPosition, int i, int j, double euclidDistance) {

this.minEuclidDistance = minEuclidDistance;

this.euclidPosition = euclidPosition;

this.i = i;

this.j = j;

this.euclidDistance = euclidDistance;

}

public double getMinEuclidDistance() {

return minEuclidDistance;

}

public int[] getEuclidPosition() {

return euclidPosition;

}

public CalcMinPoint invoke() {

if(minEuclidDistance > euclidDistance){

minEuclidDistance = euclidDistance;

if(i < j){

euclidPosition = new int[]{i,j};

}

else{

euclidPosition = new int[]{j,i};

}

}

else if(minEuclidDistance == euclidDistance){

int position0 = -1;

int position1 = -1;

if(iposition0){

euclidPosition = new int[]{position0,position1};

}

else if(euclidPosition[0] == position0 && euclidPosition[1]>position1){

euclidPosition = new int[]{position0,position1};

}

}

return this;

}

}

}