蓝桥杯 平面点集中4点最小平均距离

Question

题目描述
已知平面上若干个点的坐标。

需要求出在所有的组合中，4 个点间平均距离的最小值（四舍五入，保留 2 位小数）。
比如有 4 个点：a,b,c,d, 则平均距离是指：ab, ac, ad, bc, bd, cd 这 6 个距离的平均值。

输入描述
输入多行（可能包含上万行），每行两个数字 x，y\ （1 \leq x,y \leq 1000）x，y （1≤x,y≤1000），表示每个点的坐标。

输出描述
输出一行，在所有的组合中，4 个点间平均距离的最小值（四舍五入，保留 2 位小数）。

输入输出样例
示例
输入

10,10
20,20
80,50
10,20
20,10

输出

11.38

Answer 1

该回答引用自ChatGPT
先贴本人本地执行结果

这个是我根据chatGPT代码修改的。

最近感觉chatGPT给的代码经常有问题

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        double min = Integer.MAX_VALUE;
        //先将点存储在Point数组里面
        ArrayList<Point> list = new ArrayList<>();
        String line = "";
        while (!("").equals(line=sc.nextLine())) {
            String[] s = line.split(",");
            list.add(new Point(Integer.parseInt(s[0]), Integer.parseInt(s[1])));
        }
        //穷举所有四个点的组合
        for (int i = 0; i < list.size(); i++) {
            for (int j = i + 1; j < list.size(); j++) {
                for (int k = j + 1; k < list.size(); k++) {
                    for (int l = k + 1; l < list.size(); l++) {
                        double sum = 0;
                        //计算平均距离
                        sum += getDistance(list.get(i), list.get(j));
                        sum += getDistance(list.get(i), list.get(k));
                        sum += getDistance(list.get(i), list.get(l));
                        sum += getDistance(list.get(j), list.get(k));
                        sum += getDistance(list.get(j), list.get(l));
                        sum += getDistance(list.get(k), list.get(l));
                        sum /= 6;
                        if (sum < min) {
                            min = sum;
                        }
                    }
                }
            }
        }
        System.out.printf("%.02f", min);
    }
    //计算两点之间距离
    public static double getDistance(Point a, Point b) {
        return Math.sqrt(Math.pow(a.x - b.x, 2) + Math.pow(a.y - b.y, 2));
    }
}
class Point {
    int x;
    int y;
    public Point(int x, int y) {
        this.x = x;
        this.y = y;
    }
}

Answer 2

本题主要考虑怎么遍历每个四点组合，由于每个点有两个坐标，所以可以采用双层循环实现遍历，每两个点之间计算出距离，然后将距离加起来取平均值，比较所有的平均值，得出最小的平均值即为结果。

可以参考一下ChatGPT的实现代码：

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        double[][] points = new double[10000][2];
        int index = 0;
        while(sc.hasNextLine()){
            String[] str = sc.nextLine().split(",");
            points[index][0] = Double.parseDouble(str[0]);
            points[index][1] = Double.parseDouble(str[1]);
            index++;
        }
        double min = Double.MAX_VALUE;
        for(int i=0;i<index;i++){
            for(int j=i+1;j<index;j++){
                for(int k=j+1;k<index;k++){
                    for(int l=k+1;l<index;l++){
                        double distance = getDistance(points[i],points[j]) + getDistance(points[i],points[k]) + getDistance(points[i],points[l]) + getDistance(points[j],points[k]) + getDistance(points[j],points[l]) + getDistance(points[k],points[l]);
                        distance /= 6;
                        if(distance<min){
                            min = distance;
                        }
                    }
                }
            }
        }
        System.out.printf("%.2f\n",min);
    }
    
    private static double getDistance(double[] point1, double[] point2){
        return Math.sqrt(Math.pow(point1[0]-point2[0],2) + Math.pow(point1[1]-point2[1],2));
    }
}