问题描述

LG1337

题解

模拟退火模板

记住概率公式： \(exp(\frac{dealt}{T}) \times rand \ge R_A^ND^M_AX\)

zzk太欧了，我交了一版没过他来了一下就A了。

\(\mathrm{Code}\)

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

template <typename Tp>
void read(Tp &x){
    x=0;char ch=1;int fh;
    while(ch!='-'&&(ch>'9'||ch<'0')) ch=getchar();
    if(ch=='-') ch=getchar(),fh=-1;
    else fh=1;
    while(ch>='0'&&ch<='9') x=(x<<1)+(x<<3)+ch-'0',ch=getchar();
    x*=fh;
}

int n;
int x[1007],y[1007],w[1007];
int sx,sy;

double ansx,ansy,ans=1e18,T;
double delta=0.993;

double eps=0.00000000001;

double calc(double xxx,double yyy){
    double res=0.0;
    for(int i=1;i<=n;i++){
        double xx=xxx-x[i],yy=yyy-y[i];
        res=res+sqrt(xx*xx+yy*yy)*w[i];
    }
    return res;
}

double SA(){
    double nx=ansx,ny=ansy;
    T=2000;
    while(T>eps){
        double mx=nx+((rand()*2-RAND_MAX))*T,my=ny+(rand()*2-RAND_MAX)*T;
        double na=calc(mx,my);double del=na-ans;
        if(del<0){
            ansx=nx=mx,ansy=ny=my;
            ans=na;
        }
        else{
            if(exp(-del/T)*RAND_MAX>rand()) nx=mx,ny=my;
        }
        T*=delta;
    }
}

int ss,sss;

int main(){
    srand(192**817);
    read(n);
    for(int i=1;i<=n;i++){
        read(x[i]);read(y[i]);read(w[i]);
        ss+=x[i],sss+=y[i];
    }
    ansx=(double)ss/n;ansy=(double)sss/n;
    SA();SA();SA();SA();//SA();//SA();SA();SA();SA();SA();SA();
//  SA();SA();SA();SA();SA();SA();SA();SA();SA();SA();SA();
    printf("%.3f %.3f\n",ansx,ansy);
    return 0;
}