BZOJ 3680: 吊打XXX (广义费马点，模拟退火+爬山)
3680: 吊打XXX
Time Limit: 10 Sec Memory Limit: 128 MBSec Special Judge Submit: 2043 Solved: 732 [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
思路：
看起来是物理题。。其实就是求广义非费马点。。
也就是带权费马点。
一般的费马点是说，所有点到这个点的距离之和最小。
带权的费马点就是每个点到这个点的距离*权值，和最小。
这道题用到的才是真正的模拟退火！
模拟退火很重要的一部分就是允许有一定概率向不优的方向走，之前写的所谓的“模拟退火”的题目，全都没有体现这一点。
所以那些，其实就是一个爬山法吧。。
而且看到主席如是说...
这道题真的很棒。
初始搜索范围很大的时候用模拟退火，快速得到一个大致范围。
但是由于精度不能很好的保证，于是在做完模拟退火后在答案附近爬山。
完美的分段思想！
一直调不对样例的原因是。。。
忘记把ans初始化成最大值23333
1/* ***********************************************
2Author :111qqz
3Created Time :2016年08月31日 星期三 15时47分25秒
4File Name :code/bzoj/3680.cpp
5************************************************ */
6#include <cstdio>
7#include <cstring>
8#include <iostream>
9#include <algorithm>
10#include <vector>
11#include <queue>
12#include <set>
13#include <map>
14#include <string>
15#include <cmath>
16#include <cstdlib>
17#include <ctime>
18#define fst first
19#define sec second
20#define lson l,m,rt<<1
21#define rson m+1,r,rt<<1|1
22#define ms(a,x) memset(a,x,sizeof(a))
23typedef long long LL;
24#define pi pair < int ,int >
25#define MP make_pair
26#define INF 1E40
27#define MAX 100000
28using namespace std;
29const double eps = 1E-3;
30const int dx4[4]={1,0,0,-1};
31const int dy4[4]={0,-1,1,0};
32const int inf = 0x3f3f3f3f;
33const int N =1E4+7;
34int n;
35double Rand(){ return (rand()000)/10000.0;}
36struct point
37{
38 double x,y,w;
39 void input()
40 {
41 scanf("%lf%lf%lf",&x,&y,&w);
42 }
43 double dis(point b)
44 {
45 double res = (x-b.x)*(x-b.x)+(y-b.y)*(y-b.y);
46 return b.w*sqrt(res);
47 }
48 void look()
49 {
50 cout<<"x:"<<x<<" y:"<<y<<endl;
51 }
52}p[N],ret;
53double ans;
54double dis(const point &a,const point &b)
55{
56 return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
57}
58double Cal(point x)
59{
60 double res = 0;
61 for ( int i = 0 ; i < n ; i++) res +=x.dis(p[i]);
62 if (res<ans)
63 {
64 ret = x;
65 ans = res;
66 }
67 return res;
68}
69double SA(const point *p)
70{
71 ans = INF;
72 double step;
73 const double delta = 0.98;
74 point nxt;
75 ret.x = 0 ;
76 ret.y = 0 ;
77 for ( int i = 0 ; i < n ; i++) ret.x+=p[i].x,ret.y+=p[i].y;
78 ret.x = ret.x/double(n);
79 ret.y = ret.y/double(n);
80 ret.x = 0 ;
81 ret.y = 0 ;
82 point cur = ret;
83 // cur.look();
84 for (step = MAX ; step>eps ; step*=delta){
85 nxt.x = cur.x + (Rand()*2-1.0)*step;
86 nxt.y = cur.y + (Rand()*2-1.0)*step;
87 // nxt.look();
88 // ret.look();
89 double delta = Cal(cur)-Cal(nxt);
90 if (delta>0||exp(delta/step)>Rand()) cur = nxt;
91 }
92 for ( int i = 1 ; i <=1000 ; i++)
93 {
94 point nxt;
95 nxt.x = ret.x+(Rand()*2-1.0)*step; //在模拟退火得到的答案附近用爬山法微调，增加精确度。
96 nxt.y = ret.y+(Rand()*2-1.0)*step;
97 Cal(nxt);
98 }
99 return ans;
100}
101int main()
102{
103 #ifndef ONLINE_JUDGE
104 freopen("code/in.txt","r",stdin);
105 #endif
106 srand(821452);
107 scanf("%d",&n);
108 for ( int i = 0 ; i < n ; i++) p[i].input();
109 SA(p);
110 printf("%.3f %.3f\n",ret.x,ret.y);
111 #ifndef ONLINE_JUDGE
112 fclose(stdin);
113 #endif
114 return 0;
115}