[BZOJ3680]吊打XXX(模拟退火)

3680: 吊打XXX
Time Limit: 10 Sec Memory Limit: 128 MBSec Special Judge
Submit: 4404 Solved: 1622
[Submit][Status][Discuss]
Description

gty又虐了一场比赛，被虐的蒟蒻们决定吊打gty。gty见大势不好机智的分出了n个分身，但还是被人多势众的蒟蒻抓住了。蒟蒻们将
n个gty吊在n根绳子上，每根绳子穿过天台的一个洞。这n根绳子有一个公共的绳结x。吊好gty后蒟蒻们发现由于每个gty重力不同，绳
结x在移动。蒟蒻wangxz脑洞大开的决定计算出x最后停留处的坐标，由于他太弱了决定向你求助。
不计摩擦，不计能量损失，由于gty足够矮所以不会掉到地上。

Input

输入第一行为一个正整数n(1<=n<=10000)，表示gty的数目。
接下来n行,每行三个整数xi，yi，wi，表示第i个gty的横坐标，纵坐标和重力。
对于20%的数据，gty排列成一条直线。
对于50%的数据，1<=n<=1000。
对于100%的数据，1<=n<=10000,-100000<=xi,yi<=100000

Output

输出1行两个浮点数（保留到小数点后3位），表示最终x的横、纵坐标。

Sample Input

3
0 0 1
0 2 1
1 1 1

Sample Output

0.577 1.000

HINT

Source

By wangxz

[Submit][Status][Discuss]

求二维点加权平均数的最小值，说复杂点就是根据“能量总是在降低”理论得出的广义费马点。

模拟退火，每次跳跃幅度与T成正比，然后以$e^frac{Delta}{T}$的概率接受更劣值（温度越低接受概率越大）。

https://www.cnblogs.com/JoeFan/p/4341029.html

调一调参数就好，一般提答题用的比较多，记得设为与系统时间戳有关的随机种子，这样多次对于多次提交去最大值的赛制会较有利。

 1 #include<cmath>
 2 #include<cstdio>
 3 #include<algorithm>
 4 #define rep(i,l,r) for (int i=l; i<=r; i++)
 5 typedef double db;
 6 using namespace std;
 7 
 8 const int N=10010;
 9 int n;
10 db Ansx,Ansy,D,X[N],Y[N],W[N];
11 
12 inline db sqr(db x){ return x*x; }
13 inline db Dis(db x1,db y1,db x2,db y2){ return sqrt(sqr(x2-x1)+sqr(y2-y1)); }
14 inline db Rand(){ return (db)(rand()%10000)/10000.0; }
15  
16 db calc(db x,db y){
17     db res=0;
18     rep(i,1,n) res+=W[i]*Dis(x,y,X[i],Y[i]);
19     if (res<D) D=res,Ansx=x,Ansy=y;
20     return res;
21 }
22 
23 void solve(){
24     db Delta,T=100000,Nowx=Ansx,Nowy=Ansy,Nx,Ny;
25     while (T>0.001){
26         Nx=Nowx+T*(Rand()*2-1); Ny=Nowy+T*(Rand()*2-1);
27         Delta=calc(Nowx,Nowy)-calc(Nx,Ny);
28         if (Delta>0 || exp(Delta/T)>Rand()) Nowx=Nx,Nowy=Ny;
29         T*=0.97;
30     }
31     rep(i,1,1000) Nx=Ansx+T*(Rand()*2-1),Ny=Ansy+T*((Rand()*2)-1),calc(Nx,Ny);
32 }
33 
34 int main(){
35     freopen("bzoj3680.in","r",stdin);
36     freopen("bzoj3680.out","w",stdout);
37     srand(20020223); scanf("%d",&n);
38     rep(i,1,n) scanf("%lf%lf%lf",&X[i],&Y[i],&W[i]),Ansx+=X[i],Ansy+=Y[i];
39     Ansx/=(db)n; Ansy/=(db)n; D=calc(Ansx,Ansy);
40     solve(); printf("%.3lf %.3lf
",Ansx,Ansy);
41     return 0;
42 }