Brief description :

。广义费马点。。）

Analysis :

。。略。。（。。这个题可以向很多方向推广。。一个比较难的方向是允许放置多个 hub 。。。

const int I = 1, L = 100, W = 65536;
const DB V = 0.9;

// I: 初始点数
// L: 迭代次数
// V: 降火速率。。

const int N = 109, C = 10000;
Po P[N]; int X, Y; Po res; DB ans;
int n;

bool check(Po p){
    return p.x >= 0 && p.y >= 0 && p.x <= C && p.y <= C;
}

DB f(Po p){
    DB res = 0; REP(i, n) res += dist(P[i], p);
    return res;
}

void SA(){

    ans = OO; DO_C(I){

        Po cur = Po(C / 2, C / 2);
        DB T = C / 2, best = f(cur);

        while (T > EPS){

            bool improved = false;

            Po pre = cur; DO_C(L){
                DB theta = (DB) (rand() % W) / W * (2*PI);
                Po suc = pre + Po(cos(theta), sin(theta)) * T;
                DB temp = f(suc);
                if (temp < best){
                    improved = true;
                    best = temp, cur = suc;
                }
            }

            if (!improved) T *= V;
        }

        if (best < ans){
            ans = best, res = cur;
        }
    }
}

int main(){

#ifdef LOCAL
    freopen("in.txt", "r", stdin);
#endif

    while (scanf("%d", &n) != EOF && n){
        REP(i, n) P[i].input();
        SA(); OT(ans);
    }
}

External link:

http://poj.org/problem?id=2420

Posted by xiaodao
Category: POJ
Tags: 模拟退火