740
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;
}
最後更新：2017-04-03 18:52:08