交了1e9次,无果,20分求助
查看原帖
交了1e9次,无果,20分求助
174806
xbb2楼主2021/7/15 21:11
#include<bits/stdc++.h>
using namespace std;
const int maxn=20005;
double x1[maxn],y11[maxn],r1[maxn],x2[maxn],y2[maxn];
double n;
double m;
double r;
double Rand(){return (double)rand()/RAND_MAX;}
double getsum(double x,double y,double x1,double y1){
	return sqrt((x-x1)*(x-x1)+(y-y1)*(y-y1));
}
double get2(double x,double y){
	double rr;
	for(int i=1;i<=n;i++){
		rr=max(getsum(x,y,x1[i],y11[i])-r1[i],rr);
	}
	rr=min(r,rr);
	//printf("%lf",rr);
	double ans=0;
	for(int i=1;i<=m;i++){
		if(getsum(x,y,x2[i],y2[i])<=rr){
			ans+=1;
		}
	}
	return ans;
}
double ans=0;
double sumx=0;
double sumy=0;
void SA(){
	for(int i=1;(double)clock() / CLOCKS_PER_SEC <= 0.95;i++){
		double ax=sumx/m;
		double ay=sumy/m;
		double T;
		double ansx,ansy;
		ans=get2(ansx,ansy);
		for(T=2605;T>=0.00001;T*=0.9972){
			double x=ansx+((rand()<<1)-RAND_MAX)*T;
			double y=ansy+((rand()<<1)-RAND_MAX)*T;
			double ansnew=get2(x,y);
			double del=ansnew-ans;
			if(del>0){
				ax=x;
				ay=y;
				ans=ansnew;
				ansx=x;
				ansy=y;
			}
			else{
				if(exp(-del/T)*RAND_MAX<rand()){
					//ans=ansnew;
					ansx=x;
					ansy=y;
				}
			}
		}
	}
}
int main(){
 	//freopen("P5544.in","r",stdin);
	//srand(time(NULL));
	srand(1e9 + 7);
	cin>>n>>m>>r;
	for(int i=1;i<=n;i++)scanf("%lf%lf",&x1[i],&y11[i],&r1[i]);
	for(int i=1;i<=m;i++)scanf("%lf%lf",&x2[i],&y2[i]),sumx+=x2[i],sumy+=y2[i];
	SA();
	printf("%.0lf",ans);
	return 0;
}
2021/7/15 21:11
加载中...