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

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