POJ 2420 A Star not a Tree? (费马点 爬山算法/模拟退火)

本文主要是介绍POJ 2420 A Star not a Tree? (费马点 爬山算法/模拟退火)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

http://poj.org/problem?id=2420
题意：求离给定$n$个点距离和最小的点（费马点）到这$n$个点的距离和。

学习一下传说中的爬山算法和模拟退火算法。

//爬山算法
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <cmath>
using namespace std;
const double PI=acos(-1.0);
const int MAXN=110;
double dx[4]={1,-1,0,0},dy[4]={0,0,1,-1};
int n;
struct Point
{double x,y;Point(){}Point(double _x,double _y){x=_x;y=_y;}Point operator -(const Point &b)const{return Point(x-b.x,y-b.y);}double operator ^(const Point &b)const{return x*b.y-y*b.x;}double operator *(const Point &b) const{return x*b.x+y*b.y;}void input(){scanf("%lf%lf",&x,&y);}
};
Point p[MAXN];
//距离的平方
double dist(Point a,Point b)
{return sqrt((a-b)*(a-b));
}
double calc(Point t)
{double res=0;for(int i=0;i<n;i++)res+=dist(p[i],t);return res;
}
int round_double(double number)
{return (number>0.0)?(number+0.5):(number-0.5);
}
double sx,sy;
int main()
{scanf("%d",&n);for(int i=0;i<n;i++){p[i].input();sx+=p[i].x;sy+=p[i].y;}sx/=n;sy/=n;double ans=calc(Point(sx,sy));for(double i=1e4;i>1e-3;i*=0.9){for(int j=0;j<4;j++){double tx=sx+dx[j]*i,ty=sy+dy[j]*i;double tmp=calc(Point(tx,ty));if(tmp<ans){ans=tmp;sx=tx;sy=ty;}}}printf("%d",round_double(ans));return 0;
}

这篇关于POJ 2420 A Star not a Tree? (费马点 爬山算法/模拟退火)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---