MnZn求助退火求查错
查看原帖
MnZn求助退火求查错
524782
2_6HogCycle楼主2022/11/6 09:58

求求诸位神犇看看qwq

#include<bits/stdc++.h>
using namespace std;
const int N=10010;
double xx[N],yy[N],x,y,n,m,R,p[N],q[N],f,rr[N];
double dis(double x,double y,double x2,double y2){
	double dtx=x-x2;
	double dty=y-y2;
	double ans=sqrt(dtx*dtx+dty*dty);
	return ans;
}
double func(double x,double y,double r){
	double ans=0;
	double maxr=r;
	for(int i=1;i<=n;i++){
		maxr=min(maxr,dis(x,y,xx[i],yy[i])-rr[i]);
	}
	for(int i=1;i<=m;i++){
		if(dis(x,y,p[i],q[i])<=maxr)ans++;
	}
	return ans;
}
void SA(){
	double t=2500;
	double dt=0.99;
	double eps=1e-10;
	while(t>eps){
		double dx=x+(rand()*2-RAND_MAX)*t;
		double dy=y+(rand()*2-RAND_MAX)*t;
		double df=func(dx,dy,R);
		if(df>f){
			x=dx,y=dy,f=df;
		}
		else if(exp((df-f)/t)*RAND_MAX<rand()){
			x=dx,y=dy;
		}
		t*=dt;
	}
}
int main()
{
	//freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
	scanf("%lf %lf %lf",&n,&m,&R);
	for(int i=1;i<=n;i++){
		scanf("%lf %lf %lf",&xx[i],&yy[i],&rr[i]);
		
	}
	for(int i=1;i<=m;i++){
		scanf("%lf %lf",&p[i],&q[i]);
		x+=p[i],y+=q[i];
	}
	x/=m,y/=m;
	f=func(x,y,R);
	SA();
	SA();
	SA();
	SA();
	SA();
	printf("%.0lf",f);
	//fclose(stdin);
	//fclose(stdout);
	return 0;
}

2022/11/6 09:58
加载中...