题意：给出平面上N（<=100）个点，你需要找到一个这样的点，使得这个点到N个点的距离之和尽可能小。输出这个最小的距离和（四舍五入到最近的整数）。

思路：参考博客：http://www.cnblogs.com/heaad/archive/2010/12/20/1911614.html

就和之前一道cf里可以用猴子乱序做的那道题一样感觉有点玄学…虽然知道流程是怎么样了但是就是很奇怪的感觉orz…

设置的delta初始温度下限温度的不同会得到不同的结果，所以多试几个参数去逼近答案吧（毕竟答案是最小的…（这时候样例就非常重要了…

关于爬山算法与模拟退火，有一个有趣的比喻：

爬山算法：兔子朝着比现在高的地方跳去。它找到了不远处的最高山峰。但是这座山不一定是珠穆朗玛峰。这就是爬山算法，它不能保证局部最优值就是全局最优值。

模拟退火：兔子喝醉了。它随机地跳了很长时间。这期间，它可能走向高处，也可能踏入平地。但是，它渐渐清醒了并朝最高方向跳去。这就是模拟退火。

伪代码

/*
* J(y)：在状态y时的评价函数值
* Y(i)：表示当前状态
* Y(i+1)：表示新的状态
* r： 用于控制降温的快慢
* T： 系统的温度，系统初始应该要处于一个高温的状态
* T_min ：温度的下限，若温度T达到T_min，则停止搜索
*/
while( T > T_min )
{
　　dE = J( Y(i+1) ) - J( Y(i) ) ; 

　　if ( dE >=0 ) //表达移动后得到更优解，则总是接受移动
Y(i+1) = Y(i) ; //接受从Y(i)到Y(i+1)的移动
　　else
　　{
// 函数exp( dE/T )的取值范围是(0,1) ，dE/T越大，则exp( dE/T )也
if ( exp( dE/T ) > random( 0 , 1 ) )//这里是求最大所以是>,如果是最小就是<了
Y(i+1) = Y(i) ; //接受从Y(i)到Y(i+1)的移动
　　}
　　T = r * T ; //降温退火 ，0<r<1 。r越大，降温越慢；r越小，降温越快
　　/*
　　* 若r过大，则搜索到全局最优解的可能会较高，但搜索的过程也就较长。若r过小，则搜索的过程会很快，但最终可能会达到一个局部最优值
　　*/
　　i ++ ;
}

代码：

爬山算法版：

int n;
struct point
{
    double x,y;
}p[110];
int dx[4]={0,0,-1,1};
int dy[4]={-1,1,0,0};
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 a)
{
    double sum=0;
    for(int i=0;i<n;i++)
        sum+=dist(a,p[i]);
    return sum;
}
int main()
{
    scanf("%d",&n);
    for(int i=0;i<n;i++)
        scanf("%lf%lf",&p[i].x,&p[i].y);
    double maxt=100;//初始温度
    double delta=0.99;//用来控制降温的快慢
    double mint=1e-8;//温度的下限，到达该温度就停止搜索
    point pp;pp.x=0;pp.y=0;//初始的点
    point nn;
    double t=maxt;
    double ans=INF;
    while(t>mint)
    {
        for(int i=0;i<4;i++)
        {
            nn.x=pp.x+dx[i]*t;//随机步长
            nn.y=pp.y+dy[i]*t;
            double zs=getsum(nn);
            if(zs<ans)
            {
                ans=zs;
                pp=nn;
            }
        }
        t=t*delta;
    }
    printf("%d\n",(int)(ans+0.5));
    return 0;
}

模拟退火版：

int n;
struct point
{
    double x,y;
}p[110];
int dx[4]={0,0,-1,1};
int dy[4]={-1,1,0,0};
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 a)
{
    double sum=0;
    for(int i=0;i<n;i++)
        sum+=dist(a,p[i]);
    return sum;
}
int main()
{
    srand(time(NULL));
    scanf("%d",&n);
    for(int i=0;i<n;i++)
        scanf("%lf%lf",&p[i].x,&p[i].y);
    double maxt=400;//初始温度
    double delta=0.99;
    double mint=1e-8;//温度的下限，到达该温度就停止搜索
    point pp;pp.x=0;pp.y=0;//初始的点
    point nn;
    double t=maxt;
    double ans=INF;
    while(t>mint)
    {
        double rad=rand()%360+1;
        nn.x=pp.x+t*cos(rad);
        nn.y=pp.y+t*sin(rad);
        double zs=getsum(nn);
        if(zs<ans)//移动后得到更优的解，接受该移动
        {
            ans=zs;
            pp=nn;
        }
        else
        {
            if(exp(zs-ans)/t<rand()%100000*0.00001)//生成（0，1）之间的随机数
            {
                ans=zs;
                pp=nn;
            }
        }
        t=t*delta;
    }
    printf("%d\n",(int)(ans+0.5));
    return 0;
}