poj 2420，模拟退火算法，费马点

题目链接：http://poj.org/problem?id=2420

题意：给n个点，找出一个点，使这个点到其他所有点的距离之和最小，也就是求费马点。

参考链接：http://www.cnblogs.com/heaad/archive/2010/12/20/1911614.html

这一篇文章写的很好，我这个小白都有一点小明白了。

记一下笔记：

模拟退火： 就是在一定范围内接受一些不是最优的解，来跳出局部最优，靠近整体最优。

贴一下伪代码：

//#pragma comment(linker, "/STACK:1024000000,1024000000")

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<vector>

#include<map>

#include<deque>

#include<functional>

#include<iterator>

#include<set>

#include<utility>

#include<stack>

#include<queue>

#include<iomanip>

#include<cmath>

using namespace std;

#define N 1005

#define eps 1e-8

#define INF 1e99

#define delta 0.98

#define T 100

int dx[] = {,,-,};

int dy[] = {-,,,};

struct Point

{

    double x,y;

} p[N];

double dist (Point a,Point b)

{

    return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));

}

double GetSum(Point p[],int n,Point t)

{

    double ans = ;

    while(n--)

    {

        ans+=dist(p[n],t);

    }

    return ans;

}

double Search(Point p[],int n)

{

    Point s = p[];

    double t = T;

    double ans = INF;

    while(t>eps)

    {

        bool flag = ;

        while(flag)

        {

            flag = ;

            for(int i=; i<; i++)

            {

                Point z;

                z.x = s.x + dx[i]*t;

                z.y = s.y + dy[i]*t;

                double tp = GetSum(p,n,z);

                if(ans>tp)

                {

                    ans = tp;

                    s = z;

                    flag = ;

                }

            }

        }

        t*=delta;

    }

    return ans;

}

int main()

{

    int n;

    while(~scanf("%d",&n))

    {

        for(int i=; i<n; i++)

            scanf("%lf%lf",&p[i].x,&p[i].y);

        printf("%.0lf\n",Search(p,n));

    }

    return ;

}