自动搬运

查看原文

来自洛谷，原作者为

	chenxia25 Всё ж старается не зря...

搬运于2025-08-24 22:11:51，当前版本为作者最后更新于2021-07-07 23:48:45，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

对于一个点 $(x,y)$，先计算出在不碰到建筑物的限制下能取的最大半径，然后通过这个半径容易算出可以杀死多少个敌人。考虑对这个 $(x,y)$ 退火。

然后如果直接把这个杀死敌人个数当作参考的话，这是个整值，导致整个二维函数很不平滑，模拟退火的效果会非常不好（形象理解一下，地图上大量充斥着 $0$，很可能走不出去）。

我们考虑设一个返回值为实数的平滑的函数，能对「即使当前点杀死敌人数量是 $0$，那么它离 $1$ 有多近」有良好的参考。「当前点对应的最大半径还需再增加多少能碰到第一个敌人」是一个好的选择，设它为 $r_0$，考虑将它纳入函数的组成部分。同时杀死敌人数量又不能不考虑，于是设这样一个估价函数 $f(x,y)=-cr_0+cnt$，其中 $c$ 是待定系数，$cnt$ 是杀死敌人数量，用该函数来退火。

那么显然要么 $r_0=0$ 要么 $cnt=0$。当 $cnt=0$ 的时候，甚至可以证明 $f$ 在这些区域上是连续的（

另外看题解学到了新招：在退火的过程中可以将每次的答案都记录下来取 max，instead of 只取最后一次。这样是严格优于只取最后一次的，因为这样甚至不带来任何时间复杂度上的增加。

经过辛苦的尝试，取 $r_0=14.14,T_0=1e12,T_e=10^{-8},\Delta T=0.9996$ 效果较好。考虑到函数有部分离散的存在，可以在卡时和只跑一次之间取个平均：跑个五次以内。而上述参数只允许跑 3 次。接下来就是随机种子的事情了。取 20060617 跑两遍只有 #2 #3 没 AC，取 12 跑一遍这两个点都 AC 了，但是又有其他点没 AC。那合起来跑三遍即可。

#include<bits/stdc++.h>
using namespace std;
#define urd uniform_real_distribution
#define mp make_pair
#define X first
#define Y second
mt19937 rng(20060617);
const double inf=1e12,eps=1e-5;
const int N=1010;
int n,m;double R;
double xx[N],yy[N],r[N];
double p[N],q[N];
int calc;
double f(double x,double y){
	calc=0;
	double rad=R;
	double cnt=0,mn=inf;
	for(int i=1;i<=n;i++){
		double d=sqrt((x-xx[i])*(x-xx[i])+(y-yy[i])*(y-yy[i]));
		rad=min(rad,d-r[i]);
	}
	rad=max(0.,rad);
	for(int i=1;i<=m;i++){
		double d=sqrt((x-p[i])*(x-p[i])+(y-q[i])*(y-q[i]));
		mn=min(mn,d-rad);
		cnt+=d<=rad+eps;
		calc+=d<=rad+eps;
	}
	return -max(0.,mn)*14.14+cnt;
}
int ans;
void sim_ann(double st,double ed,double dlt){
	double x=0,y=0;
	double res=f(x,y);
	for(double tem=st;tem>=ed;tem*=dlt){
		double nw_x=x+urd<>(-10,10)(rng)*tem;
		double nw_y=y+urd<>(-10,10)(rng)*tem;
		double nw=f(nw_x,nw_y);
		if(nw>res||urd<>(0,1)(rng)<=exp((nw-res)/tem))x=nw_x,y=nw_y,res=nw;
		ans=max(ans,calc);
//		cout<<tem<<":"<<x<<" "<<y<<" "<<res<<"!\n";
	}
}
int main(){
	cin>>n>>m>>R;
	for(int i=1;i<=n;i++)cin>>xx[i]>>yy[i]>>r[i];
	for(int i=1;i<=m;i++)cin>>p[i]>>q[i];
	sim_ann(1e12,1e-8,.9996);
	sim_ann(1e12,1e-8,.9996);
	rng=mt19937(12);
	sim_ann(1e12,1e-8,.9996);
	cout<<ans;
	return 0;
}