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

---

目录

• [TOC]

题目链接

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');

}