mxqz模拟退火
查看原帖
mxqz模拟退火
158050
fzhfzh楼主2021/5/1 13:01

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/5/1 13:01
加载中...