AOJ 1157: 大玉転がし

問題

Roll-A-Big-Ball | Aizu Online Judge

解法

大玉の通る線分 p1-p2 と障害物 minX-minY-maxX-maxY との間の最小距離は,

• p1-p2 と (minX,minY)-(minX,maxY) の距離
• p1-p2 と (minX,minY)-(maxX,minY) の距離
• p1-p2 と (maxX,minY)-(maxX,maxY) の距離
• p1-p2 と (minX,maxY)-(maxX,maxY) の距離

の最小値で得ることが出来ます。

この最小距離のところで大玉と障害物が接触しなければ大玉はその障害物と接触しません。

ということでこの問題は線分と線分の距離を求める問題に帰着しますが, それの解き方はこれを参考にしました。
線分と線分の距離

あと注意点としては, 大玉の通る線分の少なくともどちらか一方の端点が障害物の内部にある場合, 答えは必ず 0 になります(線分との距離にかかわらず)。サンプルにあるので気づくとは思いますが。

double eps = 1e-8;

double add(double a, double b) {
    if (abs(a+b) < eps * (abs(a)+abs(b))) return 0;
    return a+b;
}

bool equal(double a, double b) {
    return add(a, -b) == 0;
}

struct P {
    double x, y;
    P() {}
    P(double x, double y) : x(x), y(y) {}
    P operator+(P p) const {return P(add(x, p.x), add(y, p.y));}
    P operator-(P p) const {return P(add(x, -p.x), add(y, -p.y));}
    P operator*(double d) const {return P(x*d, y*d);}
    double dot(P p) const {return add(x*p.x, y*p.y);} // 内積
    double det(P p) const {return add(x*p.y, -y*p.x);} // 外積
    double dist(P p) const {return sqrt((x-p.x)*(x-p.x) + (y-p.y)*(y-p.y));} // 距離
    void normalize() {double d = sqrt(x*x+y*y); x /= d; y /= d;} // 正規化
    bool operator<(const P& rhs) const {
        if (x != rhs.x) return x < rhs.x;
        return y < rhs.y;
    }
    bool operator==(const P& rhs) const {
        return equal(x, rhs.x) && equal(y, rhs.y);
    }
};

// 線分p1-p2上に点qがあるかを判定する
bool on_seg(P p1, P p2, P q) {
    return (p1-q).det(p2-q) == 0 && (p1-q).dot(p2-q) <= 0;
}

// 直線p1-p2と直線q1-q2が平行かどうかの判定
bool parallel(P p1, P p2, P q1, P q2) {
    P a = p2-p1;
    P b = q2-q1;
    return a.det(b) == 0;
}

// 直線p1-p2と直線q1-q2の交点
P intersection(P p1, P p2, P q1, P q2) {
    return p1+(p2-p1)*((q2-q1).det(q1-p1)/(q2-q1).det(p2-p1));
}

inline double square(double x) {return x*x;}
// 直線p1-p2と点qの距離
double dist(P p1, P p2, P q) {
    q = q-p1;
    p2 = p2-p1;
    return sqrt((q.dot(q)*p2.dot(p2) - square(q.dot(p2))) / p2.dot(p2));
}

// 線分p1-p2と点qの距離
double distSeg(P p1, P p2, P q) {
    double d = (q-p1).dot(p2-p1) / p2.dist(p1);
    if (d < 0) return q.dist(p1);
    if (d > p2.dist(p1)) return q.dist(p2);
    return dist(p1, p2, q);
}

// 線分p1-p2と線分q1-q2の距離
double distSeg(P p1, P p2, P q1, P q2) {
    if (p1==p2 && q1==q2) return q1.dist(p1);
    if (p1==p2) return distSeg(q1, q2, p1);
    if (q1==q2) return distSeg(p1, p2, q1);
    if (!parallel(p1, p2, q1, q2)) {
        P r = intersection(p1, p2, q1, q2);
        if (on_seg(p1, p2, r) && on_seg(q1, q2, r)) return 0;
    }
    double ret = min(distSeg(p1, p2, q1), distSeg(p1, p2, q2));
    ret = min(ret, min(distSeg(q1, q2, p1), distSeg(q1, q2, p2)));
    return ret;
}

const int MAXN = 55;
int n;
int sx, sy, gx, gy;
int minX[MAXN], minY[MAXN], maxX[MAXN], maxY[MAXN], h[MAXN];
double dd[MAXN];

bool ok(double r) {
    for (int i = 0; i < n; i++) {
        double d = dd[i];
        if (r < h[i]) {
            if (r > d) return false;
        } else {
            double atMost = square(r)-square(r-h[i]);
            if (atMost > d*d) return false;
        }
    }
    return true;
}

int main() {
    while (cin >> n) {
        if (n==0) break;
        scanf("%d %d %d %d", &sx, &sy, &gx, &gy);
        for (int i = 0; i < n; i++) {
            scanf("%d %d %d %d %d", minX+i, minY+i, maxX+i, maxY+i, h+i);
        }
        for (int i = 0; i < n; i++) {
            double d = 1e9;
            d = min(d, distSeg(P(sx, sy), P(gx, gy), P(minX[i], minY[i]), P(minX[i], maxY[i])));
            d = min(d, distSeg(P(sx, sy), P(gx, gy), P(minX[i], minY[i]), P(maxX[i], minY[i])));
            d = min(d, distSeg(P(sx, sy), P(gx, gy), P(maxX[i], minY[i]), P(maxX[i], maxY[i])));
            d = min(d, distSeg(P(sx, sy), P(gx, gy), P(minX[i], maxY[i]), P(maxX[i], maxY[i])));
            dd[i] = d;
            if (minX[i] <= sx && sx <= maxX[i] && minY[i] <= sy && sy <= maxY[i]) dd[i] = 0;
            if (minX[i] <= gx && gx <= maxX[i] && minY[i] <= gy && gy <= maxY[i]) dd[i] = 0;
        }
        const double dr = 0.001/2;
        bool finish = false;
        for (double r = 1000; r > dr; r -= dr) {
            if (ok(r)) {
                printf("%.5lf\n", r);
                finish = true;
                break;
            }
        }
        if (!finish) printf("0\n");
    }
    return 0;
}