虽然说考前不应该碰这些随机化算法，容易影响思考，但是还是写一写吧，对于一些问题还是很好用的。
概念
什么是模拟退火。一句话解释，我们从一个旧状态随机出一个新状态，要从旧状态转移到新状态，如果新状态小于旧状态那么就接受，否则以一定概率接受这个新状态。
感觉这个解释很好理解啊！我们直接来看例题吧。
应用——计算几何
这道题题面描述写的比较阴间，大概意思就是给定你 \(n\) 个点，每个点有一个质量 \(m_i\)，然后你要找一个点 \(x\) 使得 \(\sum_{i=1}^n m_i \times \text{dist}_{i,x}\) 其中 \(\text{dis}_{i,x}\) 表示 \(i\) 和 \(x\) 之间的距离。 这你就可以直接退火了。
模拟退火你要考虑清楚两个问题，第一个是初始状态，第二个是计算代价。
那么这道题的初始状态是什么？其实初始状态你想设啥设啥，但是你为了让答案更加准确，需要设定一个尽量优的解。所以我们令初始状态是给定的坐标的平均数。
提供一个我觉得还不错的模板，后面变形要用。
#include<bits/stdc++.h>
using namespace std;
#define temp 1e5
#define cold 0.996
const int N=1e5+10;
int n;
double ans,ansx,ansy;
struct node{
int x,y,w;
}a[N];
double cost(double x,double y)//计算代价
{
double energy=0.0;
for(int i=1;i<=n;i++)
{
energy+=sqrt((x-a[i].x)*(x-a[i].x)+(y-a[i].y)*(y-a[i].y))*a[i].w;
}
return energy;
}
void SA()
{
double t=temp;//初始温度
while(t>1e-18)//退火
{
double tmpx=ansx+(rand()+rand()-RAND_MAX)*t,tmpy=ansy+(rand()+rand()-RAND_MAX)*t;
double tmp=cost(tmpx,tmpy);
double d=tmp-ans;
if(d<0.0)ans=tmp,ansx=tmpx,ansy=tmpy;//如果更优直接接受
else if(exp(-d/t)*RAND_MAX>rand())ansx=tmpx,ansy=tmpy;//否则以一定概率接受
t*=cold;//降温
}
}
void solve()
{
ans=cost(ansx,ansy);
SA();
SA();
SA();
SA();
SA();
SA();
}
int main()
{
srand(time(0));
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i].x;
cin>>a[i].y;
cin>>a[i].w;
ansx+=a[i].x;
ansy+=a[i].y;
}
ansx/=n;
ansy/=n;//初始状态
solve();
printf("%.3lf %.3lf\n",ansx,ansy);
return 0;
}