这道题就是一道裸的模拟退火。
随机枚举一点$(x,y)$作为炸弹中心,然后判断合法范围内有多少敌人就好了。
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<ctime>
#include<map>
#include<cstdlib>
#include<vector>
#define gc getchar()
#define ll long long
#define ull unsigned long long
#define file(s) freopen(s".in","r",stdin);freopen(s".out","w",stdout)
#define I inline
using namespace std;
const int N=2e3+5,mod=1e9+7;
const ull p0=31,p1=37;
template<class o>I void qr(o &x)
{
char c=gc;int f=1;x=0;
while(c<'0'||c>'9'){if(c=='-')f=-1;c=gc;}
while(c>='0'&&c<='9'){x=x*10+(c^48);c=gc;}
x*=f;
}
template<class o>I void qw(o x)
{
if(x<0)x=-x,putchar('-');
if(x/10)qw(x/10);
putchar(x%10+48);
}
int n,m,R;
int X[N],Y[N],r[N],p[N],q[N];
double rd(){return 1.0*rand()/RAND_MAX;}
void randpos(double &x,double &y)
{
x=1.0*2*R*rd()-R;
y=1.0*2*R*rd()-R;
}
#define dt 0.998
#define eps 1e-2
double dis(double x1,double y1,double x2,double y2){return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));}
int calc(double x,double y)
{
int ans=0;
double tr=R;
for(int i=1;i<=n;i++)
tr=min(tr,dis(1.0*X[i],1.0*Y[i],x,y)-r[i]);
if(tr<0)return 0;
for(int i=1;i<=m;i++)
if(dis(x,y,1.0*p[i],1.0*q[i])<=tr)ans++;
return ans;
}
int solve(double x,double y)
{
int mx=calc(x,y);
int now=mx;
double T=R;
for(;T>eps;T*=dt)
{
double nt=T+0.1;
double nx=x+(2.0*nt)*rd()-nt,ny=y+(2*nt)*rd()-nt;
int nans=calc(nx,ny);
if(nans>mx||exp(1e4*(nans-now)/T)>rd())x=nx,y=ny,now=nans;
mx=max(mx,now);
}
return mx;
}
int main()
{
srand(rand()*rand());
qr(n),qr(m),qr(R);
for(int i=1;i<=n;i++)qr(X[i]),qr(Y[i]),qr(r[i]);
for(int i=1;i<=m;i++)
qr(p[i]),qr(q[i]);
int ans=0;
double px,py;
for(int i=1;i<=20;i++)
{
randpos(px,py);
ans=max(ans,solve(px,py));
}
qw(ans);puts("");
return 0;
}
最后一次更新于2020-05-21
0 条评论