学步园

题意:

求多边形的费马点, 输出该点到所有顶点的连线长.

思路:

模拟退火.

学习模板:

/*
参考：http://blog.sina.com.cn/s/blog_64675f540100sehz.html

模拟退火的过程
1 找到这些点所在的范围，用两个点框定（代码中e1，e2两个点)
2 在这个范围内生成NUM个点（NUM自定）
3 对于每个生成的点i，在其周围(横纵坐标±D的正方形)生成NUM个点，一旦有点优于i，则替换。
4 缩小范围D，若D<精度，退出，否则执行 3
5 遍历所有NUM个点，找到val的最大值
*/

#include <cstdio>
#include <cmath>
#include <cstring>
#include <string>
#include <algorithm>
#include <ctime>
using namespace std;
const int NUM=30;
const int RAD=1000;
struct point
{
    double x,y,val;
    point() {}
    point(double _x,double _y):x(_x),y(_y) {}
} p[101],May[NUM],e1,e2;
int n;
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 judge(point t)//评价函数，得到点t的评价值val
{
    double len=0;
    for(int i=0; i<n; i++)
        len+=dis(t,p[i]);
    return len;
}
double Rand()
{
    return rand()%(RAD+1)/(1.0*RAD);   //随机产生0-1的浮点数
}
point Rand_point(point a,point b)//在a,b框定的四边形内随机生成点
{
    point tmp=point(a.x+(b.x-a.x)*Rand(),a.y+(b.y-a.y)*Rand());
    tmp.val=judge(tmp);
    return tmp;
}
void solve(double D)
{
    for(int i=0; i<NUM; i++)
        May[i]=Rand_point(e1,e2);//步骤2
    while(D>0.1)//步骤 3
    {
        for(int i=0; i<NUM; i++)
            for(int j=0; j<NUM; j++)
            {
                point tmp=Rand_point(point(May[i].x-D,May[i].y-D),
                                     point(May[i].x+D,May[i].y+D));
                if(tmp.val<May[i].val)
                {
                    May[i]=tmp;
                }
            }
        D*=0.9;
    }
    double ans=1LL<<45;
    for(int i=0; i<NUM; i++)
        if(May[i].val<ans)
            ans=May[i].val;
    printf("%0.f\n",ans);
}
int main()
{
    srand(time(0));
    e1=point(10001,10001);
    e2=point(-10001,-10001);
    while(scanf("%d",&n)==1)
    {
        for(int i=0; i<n; i++)
        {
            scanf("%lf%lf",&p[i].x,&p[i].y);
            e1.x=min(e1.x,p[i].x);//框定初始范围
            e1.y=min(e1.y,p[i].y);
            e2.x=max(e2.x,p[i].x);
            e2.y=max(e2.y,p[i].y);
        }
        solve(max(e2.y-e1.y,e2.x-e1.x));
    }
}

附:

有趣的比喻

局部搜索，模拟退火，遗传算法，禁忌搜索的形象比喻：
　　
　　
　　为了找出地球上最高的山，一群有志气的兔子们开始想办法。
　　
　　
　　1．兔子朝着比现在高的地方跳去。他们找到了不远处的最高山峰。但是这座山不一定是珠穆朗玛峰。这就是局部搜索，它不能保证局部最优值就是全局最优值。
　　
　　
　　2．兔子喝醉了。他随机地跳了很长时间。这期间，它可能走向高处，也可能踏入平地。但是，他渐渐清醒了并朝最高方向跳去。这就是模拟退火。
　　
　　
　　3．兔子们吃了失忆药片，并被发射到太空，然后随机落到了地球上的某些地方。他们不知道自己的使命是什么。但是，如果你过几年就杀死一部分海拔低的兔子，多产的-兔子们自己就会找到珠穆朗玛峰。这就是遗传算法。
　　
　　
　　4.兔子们知道一个兔的力量是渺小的。他们互相转告着，哪里的山已经找过，并且找过的每一座山他们都留下一只兔子做记号。他们制定了下一步去哪里寻找的策略。这-就是禁忌搜索。