题目链接:http://poj.org/problem?id=2420
题目大意:
给n个点,找出一个点,使这个点到其他所有点的距离之和最小,也就是求费马点。

这个点不要求在给出的点中找。

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<string>
#include<vector>
#include<stack>
#include<bitset>
#include<cstdlib>
#include<cmath>
#include<set>
#include<list>
#include<deque>
#include<map>
#include<queue>
#define LL long long
using namespace std;

struct node{
    int x, y;

}a[1005], root;

int n;
double ans=1e9, t;
const double p=0.9935;//降温系数

int xx[4]={0, 1, 0, -1}, yy[4]={1, 0, -1, 0};

double getsum(int x, int y) //计算距离和
{
    double rt=0;
    for(int i=1; i<=n; i++){
        rt+=sqrt((1.0*x-a[i].x)*(1.0*x-a[i].x)+(1.0*y-a[i].y)*(1.0*y-a[i].y));
    }
    return rt;
}

void simulate_anneal()//SA主过程
{
    int x=root.x, y=root.y;//获得当前的最优解 进行退火算法
    t=1000000;//设置温度
    while(t>1e-14)
    {
        for(int i=0; i<4; i++){

            int X=x+xx[i], Y=y+yy[i];
            double now=getsum(X, Y);
            double T=now-ans;
            if(T<0)//当前解比最优解好=接受
            {
                x=X, y=Y;
                root.x=x, root.y=y, ans=now;
            }
            else if(exp(-T/t)*RAND_MAX>rand())//没有最优解好 有一定的概率接受
            {
                x=X, y=Y;
            }
        }
        t*=p;//降温
    }
}

void solve() //多跑几遍SA,减小误差
{
    root.x=a[1].x, root.y=a[1].y;

    simulate_anneal();
    simulate_anneal();
    simulate_anneal();
}

int main()
{
    srand(1000000007);srand(rand());srand(rand());
    scanf("%d", &n);
    for(int i=1; i<=n; i++)
    {
        scanf("%d%d", &a[i].x, &a[i].y);
    }
    solve();
    printf("%.0f\n", ans);

    return 0;
}