模拟退火求调

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=1005;
int n;
struct Node{
    double x,y,w;
}a[N];
double rand(double l,double r){
    return (double)rand()/RAND_MAX*(r-l+1);
}
double calc(double x,double y){
    double res=0;
    for (int i=0;i<n;i++){
        double dx=(a[i].x-x),dy=(a[i].y-y);
        res+=sqrt(dx*dx+dy*dy)*a[i].w;
    }
    return res;
}
Node simulate_anneal(){
    Node cur;
    cur.x=0,cur.y=0;
    double tot=0;
    for (int i=0;i<n;i++) {
        cur.x+=a[i].x*a[i].w;
        cur.y+=a[i].y*a[i].w;
        tot+=a[i].w;
    }
    cur.x/=tot;
    cur.y/=tot;
    cur.w=calc(cur.x,cur.y);
    for (double T=20000;T>=1e-8;T*=0.999){
        Node now;
        now.x=rand(cur.x-T,cur.x+T);
        now.y=rand(cur.y-T,cur.y+T);
        now.w=calc(now.x,now.y);
        double dt=now.w-cur.w;
        if (dt<0) cur=now;
        else if (exp(-dt/T)>rand(0,1)) cur=now;
    }
    return cur;
}
signed main(){
    srand(19491001);
    cin>>n;Node ans;
    ans.w=1e18;
    for (int i=0;i<n;i++){
        cin>>a[i].x>>a[i].y>>a[i].w;
    }
    for (int i=1;i<=5;i++){
        Node x=simulate_anneal();
        if (x.w<ans.w) ans=x;
    }
    printf("%.3lf %.3lf",ans.x,ans.y);
    return 0;
}