模拟退火求调
查看原帖
模拟退火求调
604906
Guizy楼主2024/3/23 10:54

rt,答案不准确,但是和样例十分接近了

#include<bits/stdc++.h>
#include<random>
#include<chrono>
using namespace std;

const int Max=1001;
const double down=0.999;
int n,rx[Max],ry[Max],rw[Max];
double ansx,ansy,answ;

double check(double x,double y){
	double res=0,dx,dy;
	for(int i=1;i<=n;i++){
		dx=x-rx[i],dy=y-ry[i];
		res+=sqrt(dx*dx+dy*dy)*rw[i];
	}
	return res;
}

mt19937 rnd(random_device{}());
uniform_real_distribution<double>real_dist(0,1);

void solve(){
	double t=300000;
	while(t>1e-15){
		double ex=ansx+(real_dist(rnd)-real_dist(rnd))*t;
		double ey=ansy+(real_dist(rnd)-real_dist(rnd))*t;
		double ew=check(ex,ey);
		double det=ew-answ;
		if(det<0)
			ansx=ex,ansy=ey,answ=ew;
		else if(exp(-det/t)>real_dist(rnd))
			ansx=ex,ansy=ey,answ=ew;
		t*=down;
	}
}

int main(){
	
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d%d%d",&rx[i],&ry[i],&rw[i]);
		ansx+=rx[i],ansy+=ry[i];
	}
	ansx/=n,ansy/=n;
	answ=check(ansx,ansy);
	solve();
	
	printf("%.3lf %.3lf",ansx,ansy);
	
	return 0;
}
2024/3/23 10:54
加载中...