Luogu

LOJ

BZOJ

分析

搜了一圈似乎都写的随机算法,那就写个退火吧 /cy

对于每次随机出来的坐标 $(x,y)$,考虑如何计算答案。

首先选择的半径显然越大越好,枚举所有建筑即可算出这个最大的半径,再枚举所有敌人即可算出答案。

然而直接蒯个退火来并过不去,可以把“以一定概率接受”去掉,或者把每次随机出的那个向量的模搞小一点。

代码

// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#include <bits/stdc++.h>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=10+10,M=1000+10;

int n,m,r;
struct circle { int x,y,r; } a[N];
struct point { int x,y; } b[M];
double ansx,ansy; int ans;

inline double dis(double lx,double ly,double rx,double ry) {
    return sqrt((rx-lx)*(rx-lx)+(ry-ly)*(ry-ly));
}

inline int calc(double x,double y) {
    double R=r; int res=0;
    for (re int i=1;i<=n;++i) R=min(R,dis(x,y,a[i].x,a[i].y)-a[i].r);
    for (re int i=1;i<=m;++i) if (dis(x,y,b[i].x,b[i].y)<=R) ++res;
    return res;
}

inline void sa() {
    double x=ansx,y=ansy,T=2000;
    while (T>1e-14) {
        double X=x+((rand()<<1)-RAND_MAX)*T;
        double Y=y+((rand()<<1)-RAND_MAX)*T;
        int now=calc(X,Y);
        if (now>ans) ansx=x=X,ansy=y=Y,ans=now;
        T*=0.999;
    }
}

inline void solve() {
    ansx=0,ansy=0;
    for (re int i=1;i<=m;++i) ansx+=b[i].x,ansy+=b[i].y;
    ansx/=m,ansy/=m,ans=calc(ansx,ansy);
    sa(); sa();
}

int main() { srand(19491001);
    n=read(),m=read(),r=read();
    for (re int i=1;i<=n;++i) a[i]=(circle){read(),read(),read()};
    for (re int i=1;i<=m;++i) b[i]=(point){read(),read()};
    solve(); printf("%d\n",ans);
    return 0;
}
最后修改:2020 年 02 月 22 日 10 : 43 AM