常数275000

到n个点距离之和最小

import java.util.Random;
import java.util.Scanner;

public class Main {
    // 温度衰退率
    private static final double K = 0.99;
    // 起始温度
    private static double ST = 1000;
    // 终止温度
    private static double ET = 1e-9;

    private static final int N = 1010, L = 100;
    private static Point[] p = new Point[N];
    private static int n;

    // 计算 n 个点到当前点的距离之和
    public static double distSum(double x, double y) {
        double sum = 0;
        for (int i = 0; i < n; i++) {
            sum += Math.sqrt(Math.pow((x - p[i].x), 2) + Math.pow((y - p[i].y), 2));
        }
        return sum;
    }

    // 模拟退火的主函数
    public static double minDistSum() {
        // 初始化
        double T = ST;
        double x = 0, y = 0;
        double E = distSum(x, y);
        double ans = E;
        Random random = new Random();

        while (T > ET) {
            for (int i = 0; i < L; i++) {
                double nx = x + (random.nextDouble() * 2 - 1) * T;
                double ny = y + (random.nextDouble() * 2 - 1) * T;
                double nE = distSum(nx, ny);
                double dE = nE - E;
                if (dE < 0 || Math.exp(-dE / T) > random.nextDouble()) {
                    x = nx;
                    y = ny;
                    E = nE;
                    ans = Math.min(ans, E);// 记录最小值
                }
            }
            T *= K;
        }
        return ans;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        for (int i = 0; i < n; i++) {
            double x = sc.nextDouble(), y = sc.nextDouble();
            p[i] = new Point(x, y);
        }
        System.out.printf("%.0f", minDistSum());
    }
}

class Point {
    double x, y;

    Point(double x, double y) {
        this.x = x;
        this.y = y;
    }
}