【BZOJ3680】吊打XXX 计算几何 广义费马点+模拟退火（爬山算法）

做题之前：

令一个点到一个分身的距离为两点间的几何距离*这个分身的重力，则到所有分身的距离之和最小的点即为所求。

因此题各种参数实在太恐怖，使得模拟退火TLE/WA无数次。强烈建议此题更名为“吊打出题人”。

在此感谢网上的大神给了我们调参数的伟大参考！！！

吊打XXX C++代码实现：

[cpp] view plain copy

print?

1. #include <cmath>  
2. #include <cstdio>  
3. #include <cstring>  
4. #include <iostream>  
5. #include <algorithm>  
6. #define N 10010  
7. using namespace std;  
8. int n,x[N],y[N],w[N];double dis,ansx,ansy,xx,yy;  
9. double dist(double x1,double x2,double y1,double y2)  
10. {  
11.     return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));  
12. }  
13. int main()  
14. {  
15.     cin>>n;  
16.     for(int i=1;i<=n;i++)  
17.         scanf("%d%d%d",&x[i],&y[i],&w[i]);  
18.     double t=1000;  
19.     for(int i=1;i<=n;i++)  
20.         ansx+=x[i]*w[i],ansy+=y[i]*w[i];  
21.     ansx/=n,ansy/=n;  
22.     while(t>0.000000001)  
23.     {  
24.         xx=yy=0;  
25.         for(int i=1;i<=n;i++)  
26.             dis=dist(ansx,x[i],ansy,y[i]),  
27.             xx+=(x[i]-ansx)*w[i]/dis,  
28.             yy+=(y[i]-ansy)*w[i]/dis;  
29.         ansx+=xx*t,ansy+=yy*t;  
30.         t=t>0.5?t*0.5:t*0.98;  
31.     }  
32.     printf("%.3lf %.3lf\n",ansx,ansy);  
33.     return 0;  
34. }