poj 2420 A Star not a Tree? (模拟退火模板题求多边形费马点)

poj 2420

题意：求多边形费马点，也就是距离所有点的距离之和最小的点。

思路：模拟退火裸题。

关于模拟退火的学习： 模拟退火讲解

我就记住了一句话2333：

**爬山算法：兔子朝着比现在高的地方跳去。它找到了不远处的最高山峰。但是这座山不一定是珠穆朗玛峰。这就是爬山算法，它不能保证局部最优值就是全局最优值。**

**　 模拟退火：兔子喝醉了。它随机地跳了很长时间。这期间，它可能走向高处，也可能踏入平地。但是，它渐渐清醒了并朝最高方向跳去。**

等写一波题再来总结

以及：感觉适牛的版好简洁嘿嘿嘿。

/* ***********************************************
Author :111qqz
Created Time :2016年05月30日 星期一 17时04分06秒
File Name :code/poj/2420.cpp
************************************************ */
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <cmath>
#include <cstdlib>
#include <ctime>
#define fst first
#define sec second
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define ms(a,x) memset(a,x,sizeof(a))
typedef long long LL;
#define pi pair < int ,int >
#define MP make_pair
#define MAX  1000000
#define INF 999999999 
using namespace std;
const double eps = 1E-8;
const int dx4[4]={1,0,0,-1};
const int dy4[4]={0,-1,1,0};
const int inf = 0x3f3f3f3f;
const int N=105;
int n;
int dblcmp(double d)
{
    return d<-eps?-1:d>eps;
}
struct point
{
    double x,y;
    void input()
    {
	scanf("%lf%lf",&x,&y);
    }
    double dis(point b)
    {
	double res ;
	res = (x-b.x)*(x-b.x)+(y-b.y)*(y-b.y);
	return sqrt(res);
    }
    void look()
    {
	cout<<"x:"<<x<<" y:"<<y<<endl;
    }
}p[N];
double getsum(point t)
{
    double sum = 0.0;
    for ( int i = 1 ; i <= n ; i++) sum += t.dis(p[i]);
    return sum;
}
double SA(const point *p,int n,point &ret)
{
    int i;
    double t,cur,ans = inf;
    const double delta =0.95;
    bool tag;
    point nxt;
    for (ret = p[1] ,t=MAX;t>eps;t*=delta){
	for (tag = true;tag;){
	    for (tag = i = 0;i<4;i++){
		nxt.x = ret.x + dx4[i]*t;
		nxt.y = ret.y + dy4[i]*t;
		cur = getsum(nxt);
		if (cur<ans){
		    ans = cur;
		    ret = nxt;
		    tag = true;
		    break;
		}
	    }
	}
    }
    return ans;
}
int main()
{
	#ifndef  ONLINE_JUDGE 
	freopen("code/in.txt","r",stdin);
  #endif
	scanf("%d",&n);
	for ( int i = 1; i <= n ; i++) p[i].input();
	double ans;
	point res;
	ans = SA(p,n,res);
	printf("%0.f\n",ans);
  #ifndef ONLINE_JUDGE  
  fclose(stdin);
  #endif
    return 0;
}