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