BZOJ3680 吊打xxx

爬山。

爬山算法即是模拟爬山的过程，随机选择一个位置爬山，每次朝着更高
的方向移动，直到到达山顶，即每次都在临近的空间中选择最优解作为
当前解，直到局部最优解。这样算法会陷入局部最优解，能否得到全局
最优解取决于初始点的位置。初始点若选择在全局最优解附近，则就可
能得到全局最优解。

http://www.matrix67.com/blog/archives/422

By：大奕哥

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 int n;
 4 double ansx,ansy;
 5 struct node{
 6     double x,y;
 7     int w;
 8 }p[10005];
 9 double sqr(double x){return x*x;}
10 double dis(double x,double y,node b){
11     return sqrt(sqr(x-b.x)+sqr(y-b.y));
12 }
13 void hillclimb()
14 {
15     double t=1000,x,y;
16     for(int i=1;i<=n;++i)
17     ansx+=p[i].x*p[i].w,ansy+=p[i].y*p[i].w;
18     ansx/=n;ansy/=n;
19     while(t>1e-9)
20     {
21         x=y=0;
22         for(int i=1;i<=n;++i)
23         {
24             x+=(p[i].x-ansx)*p[i].w/dis(ansx,ansy,p[i]);
25             y+=(p[i].y-ansy)*p[i].w/dis(ansx,ansy,p[i]);
26         }
27         ansx+=x*t;ansy+=y*t;
28         if(t>0.5)t*=0.5;
29         else t*=0.97;
30     }
31     printf("%.3lf %.3lf",ansx,ansy);
32 }
33 int main()
34 {
35     scanf("%d",&n);
36     for(int i=1;i<=n;++i)
37         scanf("%lf%lf%d",&p[i].x,&p[i].y,&p[i].w);
38     hillclimb();
39     return 0;
40 }