POJ 3525. Most Distant Point from the Sea

Brief description :

凸多邊形內找距離多變形邊最遠的一點。(求能放在凸多邊形里最大圓的半徑。。)

Analysis :

。。。貌似正解是二分+半平面交判定?。。(

這裡先測下退火。。。總之這個問題產生偏離向量有兩種方法。。

1. 無差別360°隨即產生一個。。。
2. 對多邊形掃一遍加權產生一個。。。

後者存在一個 O(n) 的代價。。但是貌似可以一定程度上保證在多邊形裡面。。(考慮那種獵奇的鈍角三角形吧。。。
。。。於是我的策略是 優先採用 策略 1. 。。。當判定出界的情況下下次採用策略 2.。。)

const int N = 109, L = 200, W = 1000, _T = 3000;
const DB V = 0.8;

// L: 迭代次數
// W: 可分配權值
// _T: 初始溫度。。

// V: 降火速率。。

struct Polygon;
DB dist_sqr(Polygon, Po);

struct Polygon{
    Po P[N]; int n;

    DB dist_sqr(Po p){
        return ::dist_sqr((*this), p);
    }

    void init(int _n){
        n = _n; REP(i, n) P[i].input(); P[n] = P[0];
    }

    bool inside(Po p){
        REP(i, n) if (det(P[i], P[i+1], p) < 0) return false;
        return true;
    }

    void solve(){

        Po res; int l = 0; REP(i, n){
            int w = rand() % W + 1;
            res += w * P[i], l += w;
        }

        res /= l;

        DB T = _T, best = dist_sqr(res);

        while (T > EPS){

            bool improved = false;
            bool hard = false;

            Po pre = res, cur; DO_C(L){
                if (!hard){
                    DB theta = (DB) (rand() % W) / W * (2*PI);
                    cur = pre + Po(cos(theta), sin(theta)) * T;
                }
                else {

                    Po dir; REP(i, n){
                        int w = rand() % W + 1;
                        dir += (P[i] - pre) * w;
                    }

                    if (sgn(dir.length_sqr()) == 0) continue;
                    if (dice()) dir = - dir;

                    dir /= dir.length(), dir *= T;
                    cur = pre + dir;
                }

                if (inside(cur)){
                    DB temp = dist_sqr(cur);
                    if (temp > best){
                        improved = true;
                        res = cur, best = temp;
                    }
                    hard = false;
                }
                else
                    hard = true;
            }

            if (!improved) T *= V;
        }

        OT(sqrt(best));
    }
} P;

DB dist_sqr(Polygon Poly, Po p){
    DB res = OO; REP(i, Poly.n) res = min(res, dist_sqr(Seg(Poly.P[i], Poly.P[i+1]), p));
    return res;
}

int n;

int main(){

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

    while (true){
        if (!_RD(n)) break;
        P.init(n); P.solve();
    }
}