Luogu

分析

想一想没有什么思路,可以考虑写退火。

然后由于种种原因,正常写法的退火不太能过,把“以一定概率接受”去掉就能过了。

事实上网上大部分题解的“以一定概率接受”都等价于“不接受”。

代码

// ===================================
//   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 月 28 日 05 : 28 PM