一个疑问(省流:我的第六个点答案会偏大)
查看原帖
一个疑问(省流:我的第六个点答案会偏大)
394665
顾宁楼主2022/8/5 15:51

我写了一发爬山法 但是一直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);
}
2022/8/5 15:51
加载中...