ZigZagK的博客
[模拟退火]BZOJ3680【吊打XXX】题解
2019年3月11日 21:22
BZOJ
查看标签

题目概述

有 $n$ 个砝码,第 $i$ 个砝码在 $x_i,y_i$ ,重量为 $w_i$ 。现在把所有砝码绑在一起,求绳结平衡在哪个位置。

解题报告

玄学大法模拟退火……调参调到吐血。来Orz XZY吧!

示例程序

#include<cmath>
#include<cstdio>
#include<cstdlib>
using namespace std;
typedef long double DB;
const int maxn=10000;

int n,a[maxn+5],b[maxn+5],c[maxn+5];DB X,Y,E;

#define sqr(x) ((DB)(x)*(x))
#define dis(x,y,i) (sqrt(sqr((x)-a[i])+sqr((y)-b[i])))
inline DB getE(DB x,DB y,DB ans=0) {for (int i=1;i<=n;i++) ans+=dis(x,y,i)*c[i];return ans;}
#define Rand() ((DB)rand()/RAND_MAX)
inline void Solve(DB T){
    for (DB nowx=X,nowy=Y;T>1e-14;T*=0.975){
        DB x=nowx+(rand()*2-RAND_MAX)*T,y=nowy+(rand()*2-RAND_MAX)*T,e=getE(x,y);
        if (e<E) X=nowx=x,Y=nowy=y,E=e; else if (exp((E-e)/T)>Rand()) nowx=x,nowy=y;
    }
}
int main(){
    freopen("program.in","r",stdin);freopen("program.out","w",stdout);
    scanf("%d",&n);for (int i=1;i<=n;i++) scanf("%d%d%d",&a[i],&b[i],&c[i]);
    srand(19260817);E=getE(X,Y);for (int t=1;t<=3;t++) Solve(2333);
    printf("%.3f %.3f\n",(double)X,(double)Y);return 0;
}
版权声明:本博客所有文章除特别声明外,均采用 CC BY 4.0 CN协议 许可协议。转载请注明出处!