模拟退火

题目描述：平面上给你n个点，让你求一个点，到这n点的距离和最小。

poj2420

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();
}