P6505

用 SA 写过去了，但是有些不理解

去年写这道题的时候，用了概率转移方程，结果最高分只有 10pts

今年再来写的时候，把概率转移给注释掉了，调完参数瞬间 AC

翻了一下题解发现既有用转移方程的也有没有用转移方程的，感觉很神奇，是代码实现的不同吗？

代码贴这里了

#include<bits/stdc++.h>
#define ll long long
using namespace std;
mt19937 myrand(time(0));
const double delta=0.995;
inline ll read(){
	ll x=0,w=1;
	char ch=0;
	while(ch<'0'||ch>'9'){
		if(ch=='-')w=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9'){
		x=x*10+(ch-'0');
		ch=getchar();
	}
	return x*w;
}
inline int randint(int l,int r){
	return myrand()%(r-l+1)+l;
}
double n,w,h;
struct node{
	double x,y;
}a[1005];
struct NODE{
	double x,y,res;
}tmp,ans;
double check(){
	double ret=1e18;
	for(int i=1;i<=n;i++){
		ret=min(ret,sqrt((tmp.x-a[i].x)*(tmp.x-a[i].x)+(tmp.y-a[i].y)*(tmp.y-a[i].y)));
	}
	return ret;
}
void SA(){
	double T=2e3;
	while(T>=1e-16){
		while((double)clock()/CLOCKS_PER_SEC>0.96)break;
		tmp.x=(ans.x+(randint(0,w)*2.0-w)*T)*1.0;
		tmp.y=(ans.y+(randint(0,h)*2.0-h)*T)*1.0;
		if(tmp.x>w||tmp.y>h||tmp.x<0.0||tmp.y<0.0){T*=delta;continue;}
		double __tmp=check();
		double Delta=__tmp-ans.res;
		if(Delta>0){
			ans=tmp;
			ans.res=__tmp;
		}/*else if(exp(Delta/T)*RAND_MAX>randint(0,RAND_MAX)){
			ans.x=tmp.x;
			ans.y=tmp.y;
		}*/
		T*=delta;
	}
	/*for(int i=1;i<=200;i++){
		tmp.x=(ans.x+(randint(0,w)*2.0-w)*T)*1.0;
		tmp.y=(ans.y+(randint(0,h)*2.0-h)*T)*1.0;
		if(tmp.x>w||tmp.y>h||tmp.x<0.0||tmp.y<0.0)continue;
		double __tmp=check();
		double Delta=__tmp-ans.res;
		if(Delta>0){
			ans=tmp;
			ans.res=__tmp;
		}else if(exp(Delta/T)*RAND_MAX>randint(0,RAND_MAX)){
			ans.x=tmp.x;
			ans.y=tmp.y;
		}
	}*/
}
int main(){
	srand(time(0));
	w=read();h=read();n=read();
	for(int i=1;i<=n;i++){
		a[i].x=read()*1.0;
		a[i].y=read()*1.0;
	}
	tmp.x=ans.x=w/2.0,tmp.y=ans.y=h/2.0,ans.res=check();
	while((double)clock()/CLOCKS_PER_SEC<0.9)SA();
	printf("%.10f",ans.res);
	return 0;
}