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; }