BZOJ
Luogu
（洛谷和BZOJ上的数据范围不同，可能需要稍微调一调参数）
sol
这题的参数调得我心累
模拟退火的模型可以形象地理解为：不断降温的小球在一个凹凸不平的平面上反复横跳，根据万有引力定理小球一定会停留在一个低洼的位置。在温度高的时候小球的运动幅度剧烈，同时也较容易地会接受更劣的解（也就是一个更高的位置）。随着温度降低小球的运动幅度减小，变得较难以接受一个更劣的解。
因为这题的背景下较优解会比较集中，所以在降温达到指定温度后要向四周多rand几次。
code
#include<cstdio>#include<algorithm>#include<ctime>#include<cmath>using namespace std;const int N = 1005;struct node{double x,y,w,tot;}p[N],ans;int n;double sqr(double x){return x*x;}double dist(node a,node b){return sqrt(sqr(a.x-b.x)+sqr(a.y-b.y));}double calc(node P){ ???double res=0; ???for (int i=1;i<=n;i++) ???????res+=p[i].w*dist(P,p[i]); ???return res;}double Rand(){return rand()%100000/100000.0;}void SA(double T){ ???node now=ans,nw;double delta; ???while (T>1e-5) ???{ ???????nw.x=now.x+T*(2*Rand()-1); ???????nw.y=now.y+T*(2*Rand()-1); ???????nw.tot=calc(nw); ???????if (nw.tot<now.tot||exp((now.tot-nw.tot)/T)>Rand()) now=nw; ???????if (nw.tot<ans.tot) ans=nw; ???????T*=0.99; ???} ???for (int i=1;i<=5000;i++) ???{ ???????nw.x=ans.x+T*(2*Rand()-1); ???????nw.y=ans.y+T*(2*Rand()-1); ???????nw.tot=calc(nw); ???????if (nw.tot<ans.tot) ans=nw; ???}}int main(){ ???scanf("%d",&n); ???for (int i=1;i<=n;i++) ???{ ???????scanf("%lf %lf %lf",&p[i].x,&p[i].y,&p[i].w); ???????ans.x+=p[i].x;ans.y+=p[i].y; ???} ???ans.x/=n;ans.y/=n;ans.tot=calc(ans); ???for (int i=1;i<=10;i++) SA(100000); ???printf("%.3lf %.3lf",ans.x,ans.y); ???return 0;}