【POJ 2420】A Star not a Tree?

题目

题目链接：http://poj.org/problem?id=2420
给定一个 (n) 边形所有顶点坐标 (x,y)，求其费马点到所有顶点距离和。

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

思路

模拟退火，每次在目前最优解附近随机点。暴力 check 即可。

代码

#include <cmath>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int N=110;
const double delta=0.996;
int Q,n,sumx,sumy,X[N],Y[N];
double sx,sy,ans,sum;

double work(double x,double y)
{
	double sum=0;
	for (int i=1;i<=n;i++)
		sum+=sqrt((x-X[i])*(x-X[i])+(y-Y[i])*(y-Y[i]));
	return sum;
}

void solve()
{
	srand(rand());
	double t0=8000,t1=1e-14;
	while (t0>t1)
	{
		double x=sx+(rand()*2-RAND_MAX)*t0;
		double y=sy+(rand()*2-RAND_MAX)*t0;
		double sum=work(x,y);
		if (sum<ans) ans=sum;
		else if (exp(-(sum-ans)/t0)>1.0*rand()/RAND_MAX) sx=x,sy=y;
		t0*=delta;
	}
}

int main()
{
	while (scanf("%d",&n)!=EOF)
	{
		srand(n+sumx);
		sumx=sumy=0;
		for (int i=1;i<=n;i++)
		{
			scanf("%d%d",&X[i],&Y[i]);
			sumx+=X[i]; sumy+=Y[i];
		}
		sx=1.0*sumx/n; sy=1.0*sumy/n;
		ans=work(sx,sy);
		solve(); solve(); solve();
		printf("%d
",(int)ans);
	}
	return 0;
}