LOJ#2076. 「JSOI2016」炸弹攻击（模拟退火）

题面

传送门

题解

退火就好了

记得因为答案比较小，但是温度比较高，所以在算\(\exp\)的时候最好把相差的点数乘上一个常数来让选取更劣解的概率降低

话虽如此然而我自己打的退火答案永远是\(0\)……只好抄了一发……但是完全看不出有什么区别啊……

//minamoto

#include<bits/stdc++.h>

#define R register

#define rd ((.0+rand())/RAND_MAX)

#define inline __inline__ __attribute__((always_inline))

#define fp(i,a,b) for(R int i=(a),I=(b)+1;i<I;++i)

#define fd(i,a,b) for(R int i=(a),I=(b)-1;i>I;--i)

#define go(u) for(int i=head[u],v=e[i].v;i;i=e[i].nx,v=e[i].v)

template<class T>inline bool cmin(T&a,const T&b){return a>b?a=b,1:0;}

template<class T>inline bool cmax(T&a,const T&b){return a<b?a=b,1:0;}

using namespace std;

char buf[1<<21],*p1=buf,*p2=buf;

inline char getc(){return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;}

int read(){

    R int res,f=1;R char ch;

    while((ch=getc())>'9'||ch<'0')(ch=='-')&&(f=-1);

    for(res=ch-'0';(ch=getc())>='0'&&ch<='9';res=res*10+ch-'0');

    return res*f;

}

const int N=1005;const double eps=1e-2,D=0.997;

inline double dis(R double x,R double y,R double xx,R double yy){

	return sqrt((x-xx)*(x-xx)+(y-yy)*(y-yy));

}

struct node{int x,y,r;}p[N];int a[N],b[N],Ri,n,m;

int calc(double x,double y){

	int res=0;double r=Ri;

	fp(i,1,n)cmin(r,dis(p[i].x,p[i].y,x,y)-p[i].r);

	if(r<0)return 0;

	fp(i,1,m)if(dis(a[i],b[i],x,y)<=r)++res;

	return res;

}

inline void randpos(double &x,double &y){x=2*Ri*rd-Ri,y=2*Ri*rd-Ri;}

int solve(double x,double y){

	int mx=calc(x,y),now=mx;

	for(double T=Ri;T>eps;T*=D){

		double nt=T+0.1;

		double xx=x+2*nt*rd-nt,yy=y+2*nt*rd-nt;

		int nans=calc(xx,yy);

		if(nans>mx||exp(1e4*(nans-now)/T)>rd)x=xx,y=yy,now=nans;

		cmax(mx,nans);

	}

	return mx;

}

int main(){

	srand(time(0));

//	freopen("testdata.in","r",stdin);

	n=read(),m=read(),Ri=read();

	fp(i,1,n)p[i].x=read(),p[i].y=read(),p[i].r=read();

	fp(i,1,m)a[i]=read(),b[i]=read();

	int res=0;double x,y;

	fp(i,1,20)randpos(x,y),cmax(res,solve(x,y));

	printf("%d\n",res);

	return 0;

}