bzoj 4852 炸弹攻击

• 二维平面上的最优解问题,模拟退火是一个较为优秀的近似算法.
• 此题确定圆心后,便可 \(O(m)\) 算出收益,且最优解附近显然也较优,是连续变化的,可以直接模拟退火.
• 小技巧:这里不同答案差值比较小,而温度比较高,可以乘上一个常数,降低选取差解的概率,即满足下式时转移.出处.

#include<bits/stdc++.h>

using namespace std;

#define ll long long

#define mp make_pair

#define pii pair<int,int>

inline int read()

{

	int x=0;

	bool pos=1;

	char ch=getchar();

	for(;!isdigit(ch);ch=getchar())

		if(ch=='-')

			pos=0;

	for(;isdigit(ch);ch=getchar())

		x=x*10+ch-'0';

	return pos?x:-x;

}

struct v2{

	double x,y;

	v2(double x=0,double y=0):x(x),y(y) {}

	v2 operator + (const v2 &rhs) const

		{

			return v2(x+rhs.x,y+rhs.y);

		}

	v2 operator / (const double &rhs) const

		{

			return v2(x/rhs,y/rhs);

		}

	v2 operator - (const v2 &rhs) const

		{

			return v2(x-rhs.x,y-rhs.y);

		}

	double operator * (const v2 &rhs) const

		{

			return x*rhs.y-y*rhs.x;

		}

	double modulus()

		{

			return sqrt(x*x+y*y);

		}

};

const int MAXN=1e3+10;

int n,m;

double R;

struct Tur{

	double r;

	v2 pos;

}tur[MAXN];

v2 enemy[MAXN];

int dcmp(double x)

{

	return fabs(x)<=(1e-8)?0:(x>0?1:-1);

}

int calc(v2 centre)

{

	double r=R;

	for(int i=1;i<=n;++i)

		r=min(r,(centre-tur[i].pos).modulus()-tur[i].r);

	int res=0;

	for(int i=1;i<=m;++i)

		if(dcmp((centre-enemy[i]).modulus()-r)<=0)

			++res;

	return res;

}

double rd()

{

    return (double) rand() / RAND_MAX;

}

double randpos(double &x,double &y)

{

	x=2*R*rd()-R;

	y=2*R*rd()-R;

}

const double dt=0.998;

const double eps=1e-2;

int cnt=0;

int SA(double x,double y)

{

	int res=calc(v2(x,y));

	int cur=res;

	double T=R;

	while(T>eps)

		{

			double nt=T+0.1;

			double nx=x+ (2*nt)*rd()-nt,ny=y+(2*nt)*rd()-nt;

			int nans=calc(v2(nx,ny));

			if(nans>res || exp(1e4*(nans-cur)/T)>rd())

				{

					x=nx;

					y=ny;

					cur=nans;

				}

			res=max(res,cur);

			T*=dt;

		}

	return res;

}

int main()

{

	srand(19260817);

	scanf("%d%d%lf",&n,&m,&R);

	for(int i=1;i<=n;++i)

		scanf("%lf%lf%lf",&tur[i].pos.x,&tur[i].pos.y,&tur[i].r);

	for(int i=1;i<=m;++i)

		scanf("%lf%lf",&enemy[i].x,&enemy[i].y);

	int ans=0;

	for(int i=1;i<=20;++i)

		{

			double x,y;

			randpos(x,y);

			ans=max(ans,SA(x,y));

		}

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

	return 0;

}