3680: 吊打XXX

Time Limit: 10 Sec  Memory Limit: 128 MBSec  Special Judge

Submit: 4404  Solved: 1622

[][][]

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

[ ][ ][ ]

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

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

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

1 #include
     
       2 #include
      
        3 #include
       
         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
        
         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\n",Ansx,Ansy);41     return 0;42 }