[JSOI]平衡点

题目

luogu1337

bzoj3680

题解

模拟退火第一波题，真的是...非常玄学的一种算法 Orz

网上讲解挺多的，而我又比较弱，当然是不写题解了

鉴于当时我什么都看不懂，我的代码有比较详细的注释（水平有限，语文也不好，希望大佬们不要婊我），找找网上关于此算法的思想和实现，代码看不懂的可以看看我的（os：感觉自己真膨胀）

代码

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <cmath> 
#define N 10005
#define inf 1000000000
using namespace std; 

int n;
double w[N],px,py,En;

struct node
{
	double x,y;
	node(){}
	node(double xx,double yy) {x=xx;y=yy;}
}p[N],ans;
node operator + (node a,node b) {return node(a.x+b.x,a.y+b.y);}

double dis(node a,node b)//计算距离 
{
	return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}

double calc(node now)
{
	double cnt=0;
	for(int i=1;i<=n;i++) cnt+=w[i]*dis(now,p[i]);//计算当前状态下的总能量 
	if(cnt<En)//若当前状态更稳定 ，更新 
	{
		En=cnt;
		ans=now;
	}
	return cnt;//返回当前状态的总能量 
}

double Rand() {return (double)(rand()%10000)/10000.0;}//将rand()范围限制在0~1 
node get_SA()
{
	node now=ans,nxt;
	double t=100000,DE;
	while(t>0.0001)//当状态稳定至一定值后退出循环 
	{
		nxt=now+node(t*(Rand()*2-1),t*(Rand()*2-1));//随机选择加一个点(t不断缩小，随机点的范围也在逐渐缩小)
		DE=calc(now)-calc(nxt);//计算当前点与随机点的能量差值 
		if(DE>0||exp(DE/t)>Rand())//若随机点更优，替换当前点，同时有一定几率让并不较优的随机点替换当前点 
			now=nxt;
		t*=0.97;//???
	}
	for(int i=1;i<=1000;i++)//多算几遍更新ans，我觉得这个“几遍”比较玄学，算多了要T，算少了又WA
	{
		nxt=ans+node(t*(Rand()*2-1),t*(Rand()*2-1));
		calc(nxt); 
	}
}

int main()
{
	srand(19970815);
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%lf%lf%lf",&p[i].x,&p[i].y,&w[i]);
		px+=p[i].x;py+=p[i].y;
	}
	ans=node(px/n,py/n);//先将答案暂定为几何中心 
	En=calc(ans);//初始能量 
	get_SA();
	printf("%.3lf %.3lf",ans.x,ans.y);
	return 0;
}