分类： 随机化

首先我们认识一种算法——爬山算法。这种算法总是贪心地接受更优秀的解。
但是，我们知道，并不是所有的解都是一个单峰函数。因此我们有了非常具有魔力的模拟退火算法。
我们想到一种随机化的优化方案，就是对于一个新的解，如果是更优的，就一定接受它；否则，有概率去接受它。
然而这样并不是特别优的，因为如果概率固定，那么它很大意义上还是在瞎JB跳。我们有一种被称为「模拟退火」的算法。我们定义一个全局变量T，令瞎JB跳的概率是\(e^{\frac{\Delta ans}{T}}\)，然后我们令\(T\)不断降低，使得最后的答案趋于稳定。
我们相信，只要T足够大、尝试的次数足够多，那么总是能找到最优解。
然而，我们必须明白的是，模拟退火本质上是一种以时间换正确性的算法，因此要如何在时间和正确性之间取得平衡，就成为一个很困难的问题了。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
#include<cmath>
#include<cstdlib>
#include<ctime>
#define RD() (T*(rand()*2-RAND_MAX))
using namespace std;

typedef double db;
typedef long double ldb;
const int N=1005;
const ldb dlT=0.97;
const ldb eps=1E-14;
db x[N],y[N],w[N];
int n;
inline ldb calc(db X,db Y){
	db dx,dy,rt=0;
	for(int i=1;i<=n;++i){
		dx=x[i]-X,dy=y[i]-Y;
		rt+=sqrt(dx*dx+dy*dy)*w[i];
	}
	return rt;
}
void init(){
	scanf("%d",&n);
	db smx=0,smy=0;
	int tms=100;
	for(int i=1;i<=n;++i){
		scanf("%lf%lf%lf",x+i,y+i,w+i);
		smx+=x[i],smy+=y[i];
	}
	smx/=n,smy/=n;
	db ans,bst,x0,y0,x1,y1,nw;
	ans=bst=calc(smx,smy);
	srand(time(0));
	while(tms--){
		ans=bst,x0=smx,y0=smy;
		for(db T=100000;T>eps;T*=dlT){
			x1=x0+RD(),y1=y0+RD();
			nw=calc(x1,y1);
//			printf("%lf %lf\n",x1,y1);
			if(nw<bst){
				bst=nw;
				smx=x1,smy=y1;
			}
			if(nw<ans||(exp((ans-nw)/T)>(long double)rand()/RAND_MAX)){
				ans=nw;
				x0=x1,y0=y1;
			}
		}
	}
	printf("%.3lf %.3lf\n",smx,smy);
}
int main(){
	init();
	return 0;
}