rt,关注一枚。
如下代码已为稳定 50pts 。
#include<bits/stdc++.h>
using namespace std;
#define down 0.996
#define E(x) ((x)*(x))//平方
const int N = 15,M = 1010;
int n,m;
double R;
struct building{
double x,y,r;//建筑
}bui[N];
struct anmy{
double p,q;//敌人
}anm[M];
double st=40000.0;//初始高温
double ansx,ansy,w;
double check(double x,double y){//判断是否一定波及建筑,否则返回最大半径
double res=40000.0,dis;
for(int i=1;i<=n;i++){
dis=(E(x-bui[i].x)+E(y-bui[i].y));
if(sqrt(dis)<bui[i].r) return -1.0;
else res=min(res,sqrt(dis)-bui[i].r);
}
return res;
}
double xma=-20000,yma=-20000,xmi=20000,ymi=20000;//为了在一定范围内随机生成解
void renew(double x,double y){
xma=max(xma,x),yma=max(yma,y);
xmi=min(xmi,x),ymi=min(ymi,y);
}
void random(double &x,double &y){
x=(double)rand()/RAND_MAX*(xma-xmi)-(xma-xmi)/2;//随机生成
y=(double)rand()/RAND_MAX*(yma-ymi)-(xma-xmi)/2;
}
double val(double x,double y){//估计爆炸收益
double rad=check(x,y),res=0,dis,add=20000.0;
for(int i=1;i<=m;i++){
dis=sqrt(E(x-anm[i].p)+E(y-anm[i].q));
if(dis<rad && dis<R) res+=1.0;
else add=min(add,rad/dis);
}
if(add>=st) add=0;
w=max(res+add,w);
return res+add;
//价值分两个部分,整数部分是炸了几个,小数部分是离炸弹最近敌人的距离比例
}
void sa(){
double t=st,lax,lay;
while(t>1e-8){
lax=ansx,lay=ansy;//暂存答案
random(ansx,ansy);
while(0>check(ansx,ansy)) random(ansx,ansy);
double ne=val(ansx,ansy),de=ne-w;//直接估价
if(de>0){
w=ne;
}else if(exp(de/sqrt(t))*RAND_MAX<=rand()){//当不接受非优解时
ansx=lax,ansy=lay;//还原
}
t*=down;//降温
//调试代码
// printf("%.3lf %.3lf %.3lf\n",ansx,ansy,val(ansx,ansy));
// printf("%.3lf\n",w);
}
}
void solve(){
while(0>check(ansx,ansy)) random(ansx,ansy);
w=val(ansx,ansy);
for(int i=1;i<=50;i++){
sa();
if((double)clock()/CLOCKS_PER_SEC>=0.9) break;
}
return ;
}
int main(){
srand(20080121);
scanf("%d%d%lf",&n,&m,&R);
for(int i=1;i<=n;i++)
scanf("%lf%lf%lf",&bui[i].x,&bui[i].y,&bui[i].r),
renew(bui[i].x,bui[i].y);
for(int i=1;i<=m;i++)
scanf("%lf%lf",&anm[i].p,&anm[i].q),
renew(anm[i].p,anm[i].q),
ansx+=anm[i].p,ansy+=anm[i].q;
ansx/=m,ansy/=m;
double dex=xma-xmi,dey=yma-ymi;
xmi-=dex,ymi-=dey,xma+=dex,yma+=dey;//扩大一点随机范围
solve();
printf("%d",(int)floor(w));
return 0;
}