模拟退火（爬山）题

板子学习可以上 oi-wiki.org 搜索学习，这里针对本题讨论各种写法

首先是许多题解中存在的问题，看下面这些许多题解在判断是否接受稍劣解时的采用的代码：

Delta = nxtAns - bestAns;
if (Delta > 0) ... //接受更优解
else if(exp(-Delta/t)*RAND_MAX<rand()) ... //接受稍劣解

其实仔细想想就能发现这句else代码没有任何意义，首先既然是较劣解，那必然有 $Delta < 0$ ，所以这里的 $-Delta/t > 0$ ,因此 $exp(-Delta/t) > 1$ 无论 $Delta$ 和 $t$ 怎么取，都没有可能接受这个稍劣解。因此，其实许多题解都写成了爬山而不是退火，即只接受更优解而不按概率接受稍劣解。

然后是第二种写法：

else if (exp(delta/sqrt(tep)) > rand())

说实话有做出改变了，但依旧有极严重的问题，虽然这种写法意识到了要去掉板子中的负号，并且依据温度改变情况用 $sqrt(tep)$ 来调整思路正确也让我受到了启发，但是作者可能没有发现前者 $exp(delta/sqrt(tep) <1$ 而后者rand() 其实是在 0 到 RAND_MAX (至少32767)直接取值，成功取稍劣解的概率实际只有 $\frac{1}{RANDMAX+1}$ ，基本很少取到，而且与温度和delta都毫无瓜葛，其实没有改变爬山的本质。

那么问题来了，为啥这么多题解没一篇写对退火？我也有经过尝试，比如把第二种写法中的rand()除上RAND_MAX，不过效果并不理想，由于本题两解之间的优劣不好判断，比如同样是 0 解，你难以得知两者谁更有可能作为平台到更优解，Delta 也不够直观。导致代码很容易取到明显不可能的答案，比如x=31321414,y=-2134145 (乱敲的) ，因为可能初始时ans=0这样的ans也是0。

考虑过找出比 nxtAns-bestAns 更好的，更能体现优劣性的 Delta ，但由于本人太菜，想不出来，只好给出一种可通过本题的，稍微更像退火的写法，如下：

if (nxtAns!=0) {
	double delta=nxtAns-ans;
	if (delta>0) {
		nowX=nxtX,nowY=nxtY,ans=nxtAns;
	} else if (exp(delta*delta*delta/T)>Rand()) {
		nowX=nxtX,nowY=nxtY;
	}
}

为了放大优劣解之间的差距，采用3次方，为了解决取到过于离谱的0解而回不来，提前排除0解不取，可以通过本题。但心里还是有些不舒坦，希望能看到更好的题解，下面给出全部代码

#include "bits/stdc++.h"
using namespace std;

const double down=0.997;
int n,m,R;
int x[11],y[11],r[11];
int p[2010],q[2010],a[2010];
int ans=0;
double nowX,nowY;

double Rand() { return (double)rand() / RAND_MAX; }

bool cmp (int xx,int yy) {
	return p[xx]<p[yy];
}

double dis (double x1,double y1,int x2,int y2) {
	return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
}

bool is(double x1,double y1,int x2,int y2,double rr) {
	if (dis(x1,y1,x2,y2)-rr<=1e-10) {
		return true;
	} else {
		return false;
	}
}

int calc (double x1,double y1) {
	double r1=R;
	for (int i=1;i<=n;i++) {
		r1=min(r1,dis(x1,y1,x[i],y[i])-r[i]);
	}
	if (r1-1<1e-10) return 0;
	int re=0;
	int h=0,tmp=1;
	while (tmp) {
		if (h+tmp<=m && p[a[h+tmp]]<x1-r1-1e-10) {
			h+=tmp;
			tmp<<=1;
		} else {
			tmp>>=1;
		}
	}
	for (int i=h+1;i<=m;i++) {
		if (p[a[i]]>x1+r1+1e-10) break;
		if (is(x1,y1,p[a[i]],q[a[i]],r1)) {
			re++;
		}
	} 
	return re;
}

void solve() {
	double T=30000;
	while (T>1e-6) {
		double nxtX=nowX+T*(Rand()*2-1);
		double nxtY=nowY+T*(Rand()*2-1);
		int nxtAns=calc(nxtX,nxtY);
		if (nxtAns!=0) {
			double delta=nxtAns-ans;
			if (delta>0) {
				nowX=nxtX,nowY=nxtY,ans=nxtAns;
			} else if (exp(delta*delta*delta/T)>Rand()) {
				nowX=nxtX,nowY=nxtY;
	 		}
		}
		T*=down;
	}
}

int main() {
	srand(114514);
	scanf("%d%d%d",&n,&m,&R);
	for (int i=1;i<=n;i++) {
		scanf("%d%d%d",x+i,y+i,r+i);
	}
	for (int i=1;i<=m;i++) {
		scanf("%d%d",p+i,q+i);
		a[i]=i;
		nowX+=p[i];
		nowY+=q[i];
	}
	nowX/=m,nowY/=m;
	ans=calc(nowX,nowY);
	//cout<<ans<<endl;
	sort(a+1,a+m+1,cmp);
	for (int i=1;i<=7;i++) {
		solve();
	}
	printf("%d",ans);
	
	return 0;
}