mxqz模拟退火
查看原帖
mxqz模拟退火
158050
fzhfzh楼主2021/4/29 22:11

RT,样例会输出一些奇怪的东西或0.333 1.000

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
//#include<random>
#include<limits.h>
#include<cstdlib>
#include<ctime>
using namespace std;
int n;
double x[10005],y[10005],w[10005],ansx,ansy,diss;
double dist(double x1,double y1,double x2,double y2){
	return (double)sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
}
double count(double xx,double yy){
	double answ=0.000;
	for(int i=1;i<=n;i++){
		answ+=dist(xx,yy,x[i],y[i])*w[i];
	}
	return answ;
}
void upd(double xx,double yy){
	double tt=count(xx,yy);
	if(tt<diss){
		ansx=xx,ansy=yy;
		diss=tt;
	}
}
double rnd(){
	return ((double)(rand()))/RAND_MAX;
}
void cold(){
	double oldx=ansx,oldy=ansy,olddis=diss;
	double t=1000000;
	while(t>0.001){
		double newx=oldx+t*(rnd()*2-1),newy=oldy+t*(rnd()*2-1);
		double newdis=count(newx,newy);
		upd(newx,newy),upd(oldx,oldy);
		if(newdis<olddis){
			ansx=oldx=newx,ansy=oldy=newy,diss=olddis=newdis;
			t*=0.97;
			continue;
		}
		double derta=newdis-olddis;
		//cout<<exp(-derta/t)<<' '<<olddis<<' '<<newdis<<endl;
		if(exp(-derta / t) > rnd())ansx=oldx=newx,ansy=oldy=newy,diss=olddis=newdis;
		t*=0.97;
	}
	for(int i=1;i<=1000;i++){
		double newx=ansx+t*(rnd()*2-1),newy=ansx+t*(rnd()*2-1);
		upd(newx,newy);
	}
}
int main(){
	srand(time(0));
	//cout<<rnd();
	//cout<<dist(1,2,3,4);
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>x[i]>>y[i]>>w[i];
		ansx+=x[i],ansy+=y[i];
	}
	ansx/=n,ansy/=n,diss=count(ansx,ansy);
	while ((double)clock()/CLOCKS_PER_SEC <0.95)cold();
	printf("%.3lf %.3lf\n", ansx, ansy);
	return 0;
}
2021/4/29 22:11
加载中...