模拟退火练手好题。
模拟退火我晚上会另写一篇。
有这么几个参数:
\(T\)：初始温度
\(eps\):终止状态
\(v\):速率
\(z\):差量，即随机的答案与当前手上的答案的差量。
随机接受函数:exp(-z / T) * RAND_MAX > rand()
这题中温度设为\(200\),速率为\(0.996\)可以通过（毕竟模拟退火是一个一般非正解算法，一般在不会做的时候用。）
[JSOI2004]平衡点
#include<iostream>
#include<cstdio>
#include<ctime>
#include<cstdlib>
#include<cmath>
#define ll long long
#define N 100005
struct P{int x,y,w;}p[N];
ll n;
double ansx,ansy;
inline long double find(long double x,long double y){
double ans = 0;
for(int i = 1;i <= n;++i)
ans += std::sqrt((x - p[i].x) * (x - p[i].x) + (y - p[i].y) * (y - p[i].y)) * p[i].w;
return ans;
}
int main(){
srand((int)time(NULL));
scanf("%lld",&n);
for(int i = 1;i <= n;++i){
scanf("%d%d%d",&p[i].x,&p[i].y,&p[i].w);
ansx += p[i].x;
ansy += p[i].y;
}
ansx = (ansx) / (1.0 * n);
ansy = (ansy) / (1.0 * n);
double eps = 1e-15;
double T = 200;//初始温度
while(T > eps){//终止态
// std::cout<<T<<" "<<(rand() * 2 - RAND_MAX) * T<<std::endl;
double nowx = ansx + ((rand() * 2 - RAND_MAX) * T);//在值域[ansx - t,ansx + t];中挑选一个随机数
double nowy = ansy + ((rand() * 2 - RAND_MAX) * T); //在值域[ansy - t,ansy + t];中挑选一个随机数
long double z = find(nowx,nowy) - find(ansx,ansy);
if(z < 0)
ansx = nowx,ansy = nowy;
else
if(exp(-z / T) * RAND_MAX > rand())//随机接受
ansx = nowx,ansy = nowy;
T *= 0.997;//降温速率
}
printf("%.3lf %.3lf\n",ansx,ansy);
}