模拟退火是一种求函数最值问题的随机算法。

给定一个函数的某一初始坐标，可以拟定一个“温度”（这里主要是借用退火的物理意义），这里的温度可以理解成自变量可以取值的范围。之后在当前最优解对应的自变量的基础上，随机产生一组附加量，用当前自变量加上附加量构成一个新的点，计算该点的函数值，若该点函数值比最优解还要优，则接受该情况，同时最优解和其对应的自变量坐标也跟着改变；若该点函数值没有最优解优，则以一定概率接受它，避免无法跳出函数极值点而非最值点，这个接受的概率表示为\(e^{(+-)\Delta}，\Delta=f_1-f_2\)，若这个值大于随机生成的概率，则接受并更新这个值，否则不接受。如此往复迭代，当最优解出现的区间范围足够小时（T温度降到接近0时），结束迭代，得出的值就可能是最优解。

（粗体为该算法用到概率的地方）

代码如下

#include <bits/stdc++.h>

using namespace std;

const int maxn=1010;

const double eps=1e-15;//精度

const double d=0.998;//降温幅度

struct node{

	double x,y,w;

}p[maxn];

int n;

double ansx,ansy,t;

inline double calc(double x,double y){

	double tot=0;

	for(int i=1;i<=n;i++){

		double dx=x-p[i].x,dy=y-p[i].y;

		tot+=sqrt(dx*dx+dy*dy)*p[i].w;

	}

	return tot;

}

void SA(){

	double T=200;

	while(T>eps){

		double nowx=ansx+(2*rand()-RAND_MAX)*T;//随机生成新坐标

		double nowy=ansy+(2*rand()-RAND_MAX)*T;

		double delta=calc(nowx,nowy)-calc(ansx,ansy);

		if(delta<0)ansx=nowx,ansy=nowy;

		else if(exp(-delta/t)*RAND_MAX>rand())ansx=nowx,ansy=nowy;//以一定概率接受

		T*=d;

	}

}

int main(){

	srand((unsigned int)time(0));

	scanf("%d",&n);

	for(int i=1;i<=n;i++){

		scanf("%lf%lf%lf",&p[i].x,&p[i].y,&p[i].w);

		ansx+=p[i].x,ansy+=p[i].y;

	}

	ansx/=(double)n,ansy/=(double)n;

	SA();

	printf("%.3lf %.3lf\n",ansx,ansy);

	return 0;

}