我写了一发爬山法 但是一直wa 然后我看了一眼wa的原因:第六个点会偏大。
爬山爬的不好的话,不应该是答案偏小么 求佬帮我看一看为什么ans会偏大qwq
#include<bits/stdc++.h>
using namespace std;
int const N=12,M=1e3+10;
double const eps=1e-10,dt=0.9972;
struct stu1{
double x,y,r;
}h[N],p[M];
int n,m,ans;
double x,y,R;
inline double D(double x){ return x*x; }
int calc(double dx,double dy){
double r=R,dq; int w=0;
for(int i=1;i<=n;i++) r=min(r,sqrt(D(dx-h[i].x)+D(dy-h[i].y))-h[i].r);
for(int i=1;i<=m;i++){
dq=sqrt(D(dx-p[i].x)+D(dy-p[i].y));
// cout<<r<<' '<<dq<<endl;
if(dq<r) w++;
}
return w;
}
#define rmx RAND_MAX
int const mo=15;
inline int Rand(){
return ((rand()&mo)<<1);
}
void SA(){
double delt,w,dx,dy,tmp=1000; //因为有小数
while(tmp>eps){
tmp=tmp*dt;
dx=(x+tmp*((rand()<<1)-rmx));
dy=(y+tmp*((rand()<<1)-rmx));
// if(dx>x||dy>y) cout<<"qwq";
// else cout<<"ovo"<<endl;
w=calc(dx,dy); delt=w-ans;
if(delt>0) ans=w,x=dx,y=dy;
// else if(exp(1.0*delt/tmp)*mo>Rand()) x=dx,y=dy;
}
}
int main(){
srand(time(0));
//cout<<rmx<<endl;
scanf("%d%d%lf",&n,&m,&R);
double dx,dy,dr;
for(int i=1;i<=n;i++) scanf("%lf%lf%lf",&dx,&dy,&dr),h[i]=(stu1){dx,dy,dr};
for(int i=1;i<=m;i++) scanf("%lf%lf",&dx,&dy),p[i]=(stu1){dx,dy,0},x+=dx,y+=dy;
x/=m; y/=m;
ans=calc(x,y);
int t=10;
while(t) t--,SA();
printf("%d\n",ans);
}