目录

• 题目链接
• 题解
• 代码

题目链接

loj#2076. 「JSOI2016」炸弹攻击

题解

模拟退火
退火时，由于答案比较小，但是温度比较高
所以在算exp时最好把相差的点数乘以一个常数让选取更差的的概率降低

代码

#include<ctime> #include<cmath> #include<cstdio> ?#include<cstring> #include<algorithm>#define gc getchar() #define pc putchar inline int read() { ????int x = 0,f = 1; ?????char c = gc; ?????while(c < '0' || c > '9') c ?=gc; ?????while(c <= '9' && c >= '0') x = x * 10 + c - '0',c = gc; ?????return x * f; } void print(int x) { ???if(x < 0) { ????????pc('-'); ????????x = -x; ????} ????if(x >= 10) print(x / 10); ????pc(x % 10 + '0'); } const int maxn = 100007; ?int n,m; double R; double X[maxn],Y[maxn],r[maxn],p[maxn],q[maxn]; double rd() { ????return (double) rand() / RAND_MAX; } void randpos(double &x,double & y){ ????x = 2 * R * rd() - R; ????y = 2 * R * rd() - R; } ?#define dt 0.998 #define eps 1e-2 double dis(double x,double y,double x1,double y1) { ????return std::sqrt((x - x1) * (x - x1) + (y - y1) * (y - y1)); } int calc(double x,double y) { ????int ret = 0; ????double tr = R; ????for(int i = 1;i <= n;++ i) { ????????tr = std::min(tr,dis(X[i],Y[i],x,y) - r[i]); ????} ????if(r < 0) return 0; ????for(int i = 1;i <= m;++ i) ????????if(dis(x,y,p[i],q[i]) <= tr) ret ++; ????return ret; } int solve(double x,double y) { ???int mx = calc(x,y); ????int now = mx; ????double T = R; ????for(;T > eps;T *= dt) { ????????double nt = T + 0.1; ????????double nx = x + (2.0 * nt) * rd() - nt,ny = y + (2 * nt) * rd() - nt; ????????int nans = calc(nx,ny); ????????if(nans > mx || exp(1e4 * (nans - now) / T) > rd()) x = nx,y = ny,now = nans; ????????mx = std::max(mx,now); ?????} ????return mx; } int main() { ????srand(19991206); ????scanf("%d%d%lf",&n,&m,&R); ????for(int i = 1;i <= n;++ i) ????????scanf("%lf%lf%lf",&X[i],&Y[i],&r[i]); ????for(int i = 1;i <= m;++ i) ???????scanf("%lf%lf",p + i,q + i); ????int ans = 0 ; ???double px,py; ????for(int i = 1;i <= 20;++ i) { ????????randpos(px,py); ????????ans = std::max(ans,solve(px,py)); ????} ????print(ans); ????pc('\n'); } 

loj#2076. 「JSOI2016」炸弹攻击 模拟退火

原文地址：https://www.cnblogs.com/sssy/p/9726267.html