Brief description :

矩形内有N个坑。。求最安全的位置。。（距离最近的坑最远。。）

Analysis :

。。。继续烧啊烧啊。。

const int I = 10, L = 200, W = 36000;
const DB V = 0.8;

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

const int N = 1009;
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 <= X && p.y <= Y;
}

DB f(Po p){
    DB res = OO; REP(i, n) checkMin(res, dist_sqr(P[i], p));
    return res;
}

void SA(){

    ans = 0; DO_C(I){

        Po cur = Po(rand() % (X+1), rand() % (Y+1));
        DB T = max(X, Y) / 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 (check(suc) && 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

    Rush{
        RD(X, Y, n); REP(i, n) P[i].input();
        SA(); OT(res);
    }
}

External link:

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

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