P5544

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