模拟退火

注：本模板实际实现的是「多起点随机化爬山法（带邻域步长收缩）」——每轮在当前点周围半径 $T$ 内随机采样，仅当新解更优（hh.val < t[i].val）时才移动，并用 T*=0.5 逐步缩小搜索半径；它没有经典模拟退火中「以概率 $\exp (-\mathrm{\Delta }E/T)$ 接受劣解」的 Metropolis 准则。对本题（费马点 / 几何中位数，目标函数为凸函数）该方法即可稳定收敛并 AC。若要改造为真正的模拟退火，需在接受判断处加入概率接受劣解：将下方 solve() 中的 if (hh.val<t[i].val) t[i]=hh; 改为

double delta = hh.val - t[i].val;
if (delta < 0 || exp(-delta/T) > getdouble()) t[i] = hh;

（此时 $T$ 同时承担温度角色，冷却系数 0.5 偏快，真 SA 通常用 0.97~0.99 以保证充分的劣解探索）。

题目描述：平面上给你 $n$ 个点，让你求一个点，到这 $n$ 个点的距离之和最小（即平面上到 $n$ 点距离和最小的点，费马点 / Fermat-Weber 点）。

POJ 2420 "A Star not a Tree?"

Sample Input

4
0 0
0 10000
10000 10000
10000 0

Sample Output

28284

#define maxn (100005)
using namespace std;
const int num=20;
int n,m;
double T,xmi,ymi,xmx,ymx;
struct node
{
    double x;
    double y;
    double val;
} p[maxn],t[maxn];
double dis(double x1,double y1,double x2,double y2)
{
    return sqrt((x2-x1)*(x2-x1)+(y2-y1)*(y2-y1));
}
double getval(double x,double y)
{
    double cnt=0;
    for (int i=1; i<=n; i++)
        cnt+=dis(x,y,p[i].x,p[i].y);
    return cnt;
}
double getdouble()
{
    double tmp=(rand()%(1000+1))*1.0/1000.0;
    return tmp;
}
node getrand(double x1,double y1,double x2,double y2)
{
    double tmpx=x1+(x2-x1)*getdouble();
    double tmpy=y1+(y2-y1)*getdouble();
    node tmp;
    tmp.x=tmpx;
    tmp.y=tmpy;
    tmp.val=getval(tmp.x,tmp.y);
    return tmp;
}
void solve()
{
    int id=1;
    while(T>=0.001)
    {
        for (int i=1; i<=num; i++)
            for (int j=1; j<=num; j++)
            {
                node hh=getrand(t[i].x-T,t[i].y-T,t[i].x+T,t[i].y+T);
                if (hh.val<t[i].val)
                    t[i]=hh;
            }
        T=T*0.5;
    }
    for (int i=2; i<=num; i++)
        if (t[i].val<t[id].val)
            id=i;
    printf("%.0f\n",t[id].val);
}
int main()
{
    scanf("%d",&n);
    xmi=ymi=9999999;
    xmx=ymx=-9999999;
    for (int i=1,tmpx,tmpy; i<=n; i++)
    {
        scanf("%d%d",&tmpx,&tmpy);
        p[i].x=(double)tmpx;
        p[i].y=(double)tmpy;
        xmi=min(xmi,p[i].x);
        xmx=max(xmx,p[i].x);
        ymi=min(ymi,p[i].y);
        ymx=max(ymx,p[i].y);
    }
    T=max(xmx-xmi,ymx-ymi);
    for (int i=1; i<=num; i++)
        t[i]=getrand(xmi,ymi,xmx,ymx);
    solve();
}

复杂度：降温迭代约 ${\log }_2(T_0/0.001)$ 次（$T_0$ 为初始温度，取坐标范围的最大跨度），每次对 $num$ 个起点各做 $nu{m}^2$ 次邻域采样、每次采样求值为 $O(n)$，整体约 $O(nu{m}^2\cdot n\cdot \log (T_0/\epsilon ))$（本模板 $num=20$）。