Note: This article is available in Chinese only. 本文暂无英文版本。
View original
题意：求多边形费马点，也就是距离所有点的距离之和最小的点。
思路：模拟退火裸题。
关于模拟退火的学习： 模拟退火讲解
我就记住了一句话2333：
爬山算法：兔子朝着比现在高的地方跳去。它找到了不远处的最高山峰。但是这座山不一定是珠穆朗玛峰。这就是爬山算法，它不能保证局部最优值就是全局最优值。
** 模拟退火：兔子喝醉了。它随机地跳了很长时间。这期间，它可能走向高处，也可能踏入平地。但是，它渐渐清醒了并朝最高方向跳去。**
等写一波题再来总结
以及：感觉适牛的版好简洁嘿嘿嘿。
代码实现
1/* ***********************************************
2Author :111qqz
3Created Time :2016年05月30日 星期一 17时04分06秒
4File Name :code/poj/2420.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 MAX 1000000
27#define INF 999999999
28using namespace std;
29const double eps = 1E-8;
30const int dx4[4]={1,0,0,-1};
31const int dy4[4]={0,-1,1,0};
32const int inf = 0x3f3f3f3f;
33const int N=105;
34int n;
35int dblcmp(double d)
36{
37 return d<-eps?-1:d>eps;
38}
39struct point
40{
41 double x,y;
42 void input()
43 {
44 scanf("%lf%lf",&x,&y);
45 }
46 double dis(point b)
47 {
48 double res ;
49 res = (x-b.x)*(x-b.x)+(y-b.y)*(y-b.y);
50 return sqrt(res);
51 }
52 void look()
53 {
54 cout<<"x:"<<x<<" y:"<<y<<endl;
55 }
56}p[N];
57double getsum(point t)
58{
59 double sum = 0.0;
60 for ( int i = 1 ; i <= n ; i++) sum += t.dis(p[i]);
61 return sum;
62}
63double SA(const point *p,int n,point &ret)
64{
65 int i;
66 double t,cur,ans = inf;
67 const double delta =0.95;
68 bool tag;
69 point nxt;
70 for (ret = p[1] ,t=MAX;t>eps;t*=delta){
71 for (tag = true;tag;){
72 for (tag = i = 0;i<4;i++){
73 nxt.x = ret.x + dx4[i]*t;
74 nxt.y = ret.y + dy4[i]*t;
75 cur = getsum(nxt);
76 if (cur<ans){
77 ans = cur;
78 ret = nxt;
79 tag = true;
80 break;
81 }
82 }
83 }
84 }
85 return ans;
86}
87int main()
88{
89 #ifndef ONLINE_JUDGE
90 freopen("code/in.txt","r",stdin);
91 #endif
92 scanf("%d",&n);
93 for ( int i = 1; i <= n ; i++) p[i].input();
94 double ans;
95 point res;
96 ans = SA(p,n,res);
97 printf("%0.f\n",ans);
98 #ifndef ONLINE_JUDGE
99 fclose(stdin);
100 #endif
101 return 0;
102}