[模拟退火][UVA10228] A Star not a Tree?

好的,在h^ovny的安利下做了此题

模拟退火中的大水题，想当年联赛的时候都差点打了退火，正解貌似是三分套三分，我记得上一道三分套三分的题我就是退火水过去的...

貌似B班在讲退火这个大玄学...

这题还是比较简单的啦~

随机化坐标x,y就可以啦

然而格式错了n遍.....死的心都有了

最后输出是四舍五入！！！四舍五入！！！四舍五入！！！

两组答案中间有空行！！！有空行！！！有空行！！！

 

然后只要会退火的板子就可以啦

//LevenKoko
#include<bits/stdc++.h>

using namespace std;

inline int read(){

    int ans=,f=;char chr=getchar();

    while(!isdigit(chr)){if(chr=='-')f=-;chr=getchar();}

    while(isdigit(chr)) {ans=(ans<<)+(ans<<)+chr-;chr=getchar();}

    return ans*f;

}

int x[],y[],n;

double ansx,ansy,ans;

const double delta=0.998;

inline double DIS(double x1,double x2,double y1,double y2){return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));}

//欧几里得距离

inline double Get_Ans(double a,double b){double ans=;for(int i=;i<=n;i++)ans+=DIS(x[i],a,y[i],b);return ans;}

//当前坐标答案

inline void Fire(){//退火板子

    double T= /**/ ,fx=ansx,fy=ansy;

    while(T>1e-){

        double tx=T*(rand()*-RAND_MAX)+fx;

        double ty=T*(rand()*-RAND_MAX)+fy;//这里调参，乱调就好了（脸白的无所畏惧），但是前面的随机数一定要能够取到负值啊（虽然我没试过不取会不会炸）

        double tans=Get_Ans(tx,ty);

        double DE=tans-ans;

        if(DE<)ans=tans,fx=ansx=tx,fy=ansy=ty;

        else if(exp(-DE/T)*RAND_MAX>rand()) fx=tx,fy=ty;

        T*=delta;

    }

}

int main(){

    int T=read();

    while(T--){

        n=read();

        for(int i=;i<=n;i++)    x[i]=read(),y[i]=read();

        ansx=ansy=;ans=Get_Ans(,);

        for(int i=;i<=;i++)    Fire();

        cout<<(int)(ans+0.5);

        if(T) puts("");puts("");

    }

    return ;

}