攒RP的退火模型---UVA10228 A Star not a Tree java实现

本文主要是介绍攒RP的退火模型---UVA10228 A Star not a Tree java实现，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

题目链接：https://www.luogu.com.cn/problem/UVA10228

题目大意：

题意翻译

给定一个N边形所有顶点坐标x,y，求其费马点到所有顶点距离和

费马点是指到多边形所有顶点距离和最小的点

输入

第一行为T， T组数据

第二行正整数N，其后N行，每行两个整数x,y。

输出

每行一个数，为所求距离和，精确到整数（每组数据要多输出一个换行，最后一组不用）

输入

1
4
0 0
0 10000
10000 10000
10000 0

输出

28284

实际我也不会，代码参考
https://www.luogu.com.cn/blog/Darth-Che/mu-ni-tui-huo-xue-xi-bi-ji
出于好奇，了解一下这个玄学的算法。人家也讲得很清楚。在此只是记录一下。

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    static double ansx,ansy,ax,ay,t,ans,mockCnt;
    static double delta = 0.996;
    static int n;
    static double[][] point;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int T = Integer.parseInt(st.nextToken());
        for(int testcase = 1;testcase<=T;testcase++){
            st = new StringTokenizer(br.readLine());
            n = Integer.parseInt(st.nextToken());
            point = new double[n][2];
            ansx = ansy = ax = ay = 0;
            ans = (int)1e8;
            mockCnt = 7;
            for(int i = 0;i<n;i++){
                st = new StringTokenizer(br.readLine());
                point[i] = new double[]{Integer.parseInt(st.nextToken()),Integer.parseInt(st.nextToken())};
                ax+=point[i][0];
                ay+=point[i][1];
            }
            mock();
            System.out.print((int)ans);
            if(testcase!=T){
                System.out.println();
            }
        }
    }

    private static void mock(){
        ansx = ax/n;
        ansy = ay/n;
        for(int i = 0;i<mockCnt;i++){
            SA();
        }
    }

    private static void SA(){
        double x = ansx;
        double y = ansy;
        t = 3000;

        while (t>1e-15){
            double xx = x+(Math.random()*2-1)*t;
            double yy = y+(Math.random()*2-1)*t;
            double now = calculate(xx,yy);
            double Delta = now - ans;
            if(Delta<0){
                ansx = xx;
                ansy = yy;
                ans = now;
                x = xx;
                y = yy;
            }
            else if(Math.pow(Math.E,(-Delta/t))>Math.random()){
                x = xx;
                y = yy;
            }
            t *= delta;
        }
    }

    private static double calculate(double x,double y){
        double result = 0;
        for(int i = 0;i<point.length;i++){
            result+=Math.sqrt(Math.pow(x-point[i][0],2)+Math.pow(y-point[i][1],2));
        }
        return result;
    }
}

这篇关于攒RP的退火模型---UVA10228 A Star not a Tree java实现的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！