【模拟退火】A Star not a Tree?

随机化

传送门：POJ2420

题意：求一个n边形费马点到所有点的距离之和

思路：先随机一个点，再用模拟退火向四个方向贪心。

注意：退火的速度不要太慢，否则TLE；答案要四舍五入。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
int n,x[105],y[105];
const int dic[4][2]={{0,-1},{-1,0},{0,1},{1,0}};
double t,delta,T,xx,yy,nx,ny,sx,sy,ans;
double getdist(double xx,double yy){
	double sum=0;
	for (int i=1;i<=n;i++)
		sum+=sqrt((x[i]-xx)*(x[i]-xx)+(y[i]-yy)*(y[i]-yy));
	return sum;
}
int main(){
	scanf("%d",&n);
	for (int i=1;i<=n;i++) scanf("%d%d",&x[i],&y[i]);
	
	t=100;
	delta=0.98*1.01;
	T=1e-3;
	xx=yy=3000;
	ans=1e10;
	while (t>T){
		bool flag=1;
		while (flag){
			flag=0;
			for (int i=0;i<4;i++){
				nx=(double)xx+dic[i][0]*t; ny=(double)yy+dic[i][1]*t;
				double tp=getdist(nx,ny);
				if (ans>tp){
					ans=tp;
					flag=1;
					sx=nx; sy=ny;
				}
				if (flag){xx=sx; yy=sy;}
			}
		}
		t*=delta;
	}
	
	printf("%d\n",(int)(ans+0.5));
	
	return 0;
}