MnZn求调
查看原帖
MnZn求调
572587
cmrhhh楼主2024/7/4 11:32
#include<bits/stdc++.h>
using namespace std;
const int maxn=2e4+10;
using ll=long long;
int N,M,R,ans=0;
double x[maxn],y[maxn],r[maxn],x_[maxn],y_[maxn];
double sx,sy,sr;
double dis(double X1,double Y1,double X2,double Y2){
	double dx=X1-X2,dy=Y1-Y2;
	return sqrt(dx*dx+dy*dy);
}
double check(int nx,int ny){
	double res=R;
	for(int i=1;i<=N;++i)res=min(res,dis(nx,ny,x[i],y[i])-r[i]);
	return res;
}
int calc(double nx,double ny,double nr){
	if(nr<0)return 0;
	int res=0;
	for(int i=1;i<=M;++i)
		if(dis(nx,ny,x_[i],y_[i])<=nr)res++;
	return res;
}
void simulate_anneal(){
	double nx,ny,nr;
	for(int t=1e3;t>1e-13;t*=0.9999){
		nx=sx+(double)(rand()*2-RAND_MAX)*t;
		ny=sy+(double)(rand()*2-RAND_MAX)*t;
		double Y=calc(nx,ny,check(nx,ny));
		double d=ans-Y;
		if(d<0){
			sx=nx;
			sy=ny;
			ans=Y;
		}
		if(exp((-d/t))>(double)rand()/RAND_MAX){
			sx=nx;
			sy=ny;
		}
	}
}
int main(){
	srand(time(NULL));
	srand(rand()+20090302);
	ios::sync_with_stdio(0),cin.tie(0);
	cin>>N>>M>>R;
	for(int i=1;i<=N;++i)cin>>x[i]>>y[i]>>r[i];
	for(int i=1;i<=M;++i)cin>>x_[i]>>y_[i],sx+=x_[i],sy+=y_[i];
	sx/=M,sy/=M;
	for(int i=1;i<=1000;++i)simulate_anneal();
	cout<<ans;
	return 0;
}
2024/7/4 11:32
加载中...