• 微信公众号:美女很有趣。 工作之余,放松一下,关注即送10G+美女照片!

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

开发技术 开发技术 2周前 (04-30) 7次浏览

题目链接: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实现
喜欢 (0)