POJ 2420 模拟退火求费马点

题意求一个多边形的费马点，即到所有顶点距离和最小的那一点。

以前觉得模拟退火好高端的样子，实际就是把点往四个方向移动固定步长，知道不能移动后缩小步长继续移动，也就是随机求一个接近最优并且满足精度的解。

#include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
typedef double diy;
struct point
{
    diy x,y;
    point() {}
    point(diy _x,diy _y):x(_x),y(_y) {}
};
double step[4][2]= {0,1,0,-1,-1,0,1,0};
double dis(point a,point b)
{
    return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
double disall(point a,point *g,int n)
{
    int i=0;
    double sum=0;
    while(n--)
        sum+=dis(a,g[i++]);
    return sum;
}
double SAnnealing(point *g,int n)
{
    point t=g[0];
    int flag;
    double ret=disall(t,g,n),st;
    for(st=100; st>1e-1; st*=0.98)
    {
        flag=1;
        while(flag)
        {
            flag=0;
            for(int i=0; i<4; i++)
            {
                point now(t.x+step[i][0]*st,t.y+step[i][1]*st);
                double nowdis=disall(now,g,n);
                if(nowdis<ret)
                    t=now,flag=1,ret=nowdis;
            }
        }
    }
    return ret;
}
int main()
{
    int n;
    point data[105];
    while(~scanf("%d",&n))
    {
        for(int i=0; i<n; i++)
            scanf("%lf%lf",&data[i].x,&data[i].y);
        printf("%.0f\n",SAnnealing(data,n));
    }
    return 0;
}