模拟退火求助!
查看原帖
模拟退火求助!
1129497
sjh0626楼主2024/12/25 19:52

rt,帮忙调调参数,此代码最高30pts

#include<bits/stdc++.h>
#define sjh0626s return
#define code 0
#define ldouble long double
using namespace std;
ldouble ansx,ansy,answ,t,delta=0.997;
int n,m;
struct node{
	int x,y;
	ldouble dist;
}a[4000];
bool cmp(node x,node y){
	return x.dist<=y.dist;
}
ldouble dist(ldouble x,ldouble y,ldouble x1,ldouble y1){
	return sqrt((x-x1)*(x-x1)+(y-y1)*(y-y1));
}
ldouble now_solve(ldouble x,ldouble y){
	ldouble r=0;
	int cnt=0;
	for(int i=1;i<=n;i++){
		a[i].dist=dist(x,y,a[i].x,a[i].y);
	}
	sort(a+1,a+n+1,cmp);
	return a[m].dist;
}
void SA(){
	t=2333;
	while(t>=1e-14){
		ldouble nx=ansx+(rand()*2-RAND_MAX)*t; //New X
		ldouble ny=ansy+(rand()*2-RAND_MAX)*t; //New Y
		ldouble nw=now_solve(nx,ny);
		ldouble d=nw-answ;
		if(d<0)ansx=nx,ansy=ny,answ=nw;
		else if(exp(-d/t)*RAND_MAX>rand())ansx=nx,ansy=ny;
		t*=delta; //降温 
//		cout<<answ<<"\n";
	}
	
}
int main(){
	srand(time(0));
	cin>>n>>m;
	for(int i=1;i<=n;i++) {
		cin>>a[i].x>>a[i].y;
		ansx+=a[i].x/n,ansy+=a[i].y/n;
	}
	answ=now_solve(ansx,ansy);
	while((double)clock()/CLOCKS_PER_SEC<=0.98)SA();
	printf("%.7Lf",answ);
	sjh0626s code;
}
2024/12/25 19:52
加载中...