poj2420A Star not a Tree?(模拟退火）

链接

求某一点到其它点距离和最小，求这个和，这个点 为费马点。

做法：模拟退火

#include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<stdlib.h>
#include<vector>
#include<cmath>
#include<queue>
#include<set>
using namespace std;
#define N 100000
#define LL long long
#define INF 0xfffffff
const double eps = 1e-8;
const double pi = acos(-1.0);
const double inf = ~0u>>2;
struct point
{
    double x,y;
    point(double x=0,double y =0):x(x),y(y){}
}p[N];
int n;
int dir[4][2] = {0,1,0,-1,1,0,-1,0};
typedef point pointt;
pointt operator -(point a,point b)
{
    return point(a.x-b.x,a.y-b.y);
}
double dis(point a)
{
    return sqrt(a.x*a.x+a.y*a.y);
}
double cal(point pp)
{
    int i;
    double s = 0;
    for(i = 1; i <= n; i++)
    s+=dis(pp-p[i]);
    return s;
}
int main()
{
    int i;
    while(scanf("%d",&n)!=EOF)
    {
        double t = 10000;
        point pp = point(0,0);
        for(i =1 ; i <= n;i ++)
        {
            scanf("%lf%lf",&p[i].x,&p[i].y);
            pp.x+=p[i].x;
            pp.y+=p[i].y;
        }
        pp.x /=n;
        pp.y /=n;
        double sum = cal(pp),tmp;
        point tp,ans = pp;
        while(t>0.02)
        {
            int flag = 1;
            while(flag)
            {
                flag = 0;
                for(i =0 ; i< 4 ; i++)
                {
                    tp = point(pp.x+dir[i][0]*t,pp.y+dir[i][1]*t);
                    tmp = cal(tp);
                    if(tmp<sum)
                    {
                        sum = tmp;
                        flag = 1;
                        ans = tp;
                    }
                }
                pp = ans;
            }
            t/=2;
        }
        printf("%.0f\n",sum);
    }
    return 0;
}