ball_by_momodi.cpp

第四届百度杯预赛解题报告 武汉大学20090315

bool can_pass(const P &S, const P &T) {
    for (int i = 0; i < SZ(c); ++i) {
        if (in_circle(S, c[i]) || in_circle(T, c[i]) || segment_circle_cross(S, T, c[i])) {
            return false;
        }
    }
    for (int i = 0; i < SZ(m); ++i) {
        if (in_mtx(S, m[i]) || in_mtx(T, m[i]) || segment_mtx_cross(S, T, m[i])) {
            return false;
        }
    }
    return true;
}

bool in_arc(const P &p, const P &S, const P &T, const C &cir) {
    return sgn(cross(cir.mid, S, p)) == sgn(cross(cir.mid, S, T)) && 
        sgn(cross(cir.mid, T, p)) == sgn(cross(cir.mid, T, S));
}

P mid_arc(const P &S, const P &T, const C &cir) {
    return cir.mid + ((S + T) / 2 - cir.mid).trunc(cir.r);
}

bool circle_cross(const C &c1, const C &c2, P &a, P &b) {
    double len2 = dist2(c1.mid, c2.mid);
    if (sgn(len2 - SQR(c1.r + c2.r)) >= 0) {
        return false;
    }
    double len = sqrt(len2);
    double x = (len + (c1.r * c1.r - c2.r * c2.r) / len) / 2;
    double t = sqrt(abs(sqr(c1.r) - x * x));
    P p = c2.mid - c1.mid;
    a = c1.mid + p.trunc(x) + p.turn_left().trunc(t);
    b = c1.mid + p.trunc(x) + p.turn_right().trunc(t);
    return true;
}

bool arc_circle_cross(const P &S, const P &T, const C &cir, const C &c2) {
    if (cir.in(c2)) {
        return true;
    }
    if (c2.in(cir) || cir == c2) {
        return false;
    }
    P a, b;
    if (circle_cross(cir, c2, a, b)) {
        if (in_arc(a, S, T, cir) || in_arc(b, S, T, cir) || in_circle(mid_arc(S, T, cir), c2)) {
            return true;
        }
    }
    return false;
}

bool arc_segment_cross(const P &S, const P &T, const C &cir, const P &segment_S, const P &segment_T) {
    P a, b;
    if (line_circle_cross(segment_S, segment_T, cir, a, b)) {
        if ((in_segment(a, segment_S, segment_T) && in_arc(a, S, T, cir)) ||
                (in_segment(b, segment_S, segment_T) && in_arc(b, S, T, cir))) {
            return true;
        }
    }
    return false;
}

bool arc_mtx_cross(const P &S, const P &T, const C &cir, const Mtx &mm) {
    for (int i = 0; i < 4; ++i) {
        if (arc_segment_cross(S, T, cir, mm[i], mm[i + 1])) {
            return true;
        }
    }
    return false;
}

bool can_pass_arc(const P &a, const P &b, const C &cir) {
    for (int i = 0; i < SZ(c); ++i) {
        if (cir != c[i] && arc_circle_cross(a, b, cir, c[i])) {
            return false;
        }
    }
    for (int i = 0; i < SZ(m); ++i) {
        if (arc_mtx_cross(a, b, cir, m[i])) {
            return false;
        }
    }
    return true;
}

double findr(const double &h, const double &r) {
    if (sgn(h - r) >= 0) {
        return r;
    } else {
        return sqrt(abs(SQR(r) - SQR(r - h)));
    }
}

bool point_circle_tangent(const P &p, const C &cir, P &a, P &b) {
    double len2 = dist2(p, cir.mid);
    if (sgn(len2 - SQR(cir.r)) <= 0) {
        return false;
    }
    double len = sqrt(len2);
    double x = sqrt(abs(len * len - cir.r * cir.r));
    double h = x * cir.r / len;
    double y = sqrt(abs(cir.r * cir.r - h * h));
    a = cir.mid + (p - cir.mid).trunc(y) + (p - cir.mid).turn_left().trunc(h);
    b = cir.mid + (p - cir.mid).trunc(y) + (p - cir.mid).turn_right().trunc(h);
    return true;
}

vector<pair<P, P> > circle_tangent(const C &a, const C &b) {
    vector<pair<P, P> > ans;
    double len2 = dist2(a.mid, b.mid);
    if (sgn(len2 - SQR(a.r + b.r)) > 0) {
        double len = sqrt(len2);
        double x = len * a.r / (b.r + a.r);
        double y = len * b.r / (a.r + b.r);
        double ta = sqrt(abs(sqr(x) - sqr(a.r)));
        double ha = a.r * ta / x;
        double pa = sqrt(abs(sqr(a.r) - sqr(ha)));
        double tb = sqrt(abs(sqr(y) - sqr(b.r)));
        double hb = b.r * tb / y;
        double pb = sqrt(abs(sqr(b.r) - sqr(hb)));
        P ab = b.mid - a.mid;
        P ba = a.mid - b.mid;
        ans.push_back(make_pair(a.mid + ab.trunc(pa) + ab.turn_right().trunc(ha),
                    b.mid + ba.trunc(pb) + ba.turn_right().trunc(hb)));
        ans.push_back(make_pair(a.mid + ab.trunc(pa) + ab.turn_left().trunc(ha),
                    b.mid + ba.trunc(pb) + ba.turn_left().trunc(hb)));
    }
    if (!a.in(b) && !b.in(a) && a != b) {
        double len = sqrt(len2);
        double n = sqrt(abs(len2 - sqr(a.r - b.r)));
        double ha = a.r * n / len;
        double hb = b.r * n / len;
        double pa = sqrt(abs(sqr(a.r) - sqr(ha)));
        double pb = sqrt(abs(sqr(b.r) - sqr(hb)));
        P p = (a.r > b.r? b.mid - a.mid: a.mid - b.mid);
        ans.push_back(make_pair(a.mid + p.trunc(pa) + p.turn_right().trunc(ha), 
                    b.mid + p.trunc(pb) + p.turn_right().trunc(hb)));
        ans.push_back(make_pair(a.mid + p.trunc(pa) + p.turn_left().trunc(ha),
                    b.mid + p.trunc(pb) + p.turn_left().trunc(hb)));
    }
    return ans;
}

bool ok(double R) {
    m.clear();
    c.clear();
    for (vector<Mtx>::iterator it = mtx.begin(); it != mtx.end(); ++it) {
        double r = findr(it->h, R);
        m.push_back(Mtx(it->minx, it->maxx, it->miny - r, it->maxy + r));
        m.push_back(Mtx(it->minx - r, it->maxx + r, it->miny, it->maxy));
        c.push_back(C((*it)[0], r));
        c.push_back(C((*it)[1], r));
        c.push_back(C((*it)[2], r));
        c.push_back(C((*it)[3], r));
    }
    {
        double r = findr(H, R);
        m.push_back(Mtx(0, L, 0, r));
        m.push_back(Mtx(0, L, W - r, W));
        m.push_back(Mtx(0, r, 0, W));
        m.push_back(Mtx(L - r, L, 0, W));
    }
    id.clear();
    f.clear();
    if (S == T) {
        fprintf(stderr, "error\n");
        while (1);
    }
    if (can_pass(S, T)) {
        return true;
    }
    find_id(S);
    find_id(T);
    for (int i = 0; i < SZ(c); ++i) {
        circle_point[i].clear();
    }
    for (vector<C>::iterator it = c.begin(); it != c.end(); ++it) {
        if (on_circle(S, *it)) {
            circle_point[it - c.begin()].push_back(S);
        }
        if (on_circle(T, *it)) {
            circle_point[it - c.begin()].push_back(T);
        }
        P a, b;
        if (point_circle_tangent(S, *it, a, b)) {
            if (can_pass(S, a)) {
                if (uno(S, a)) {
                    return true;
                }
                circle_point[it - c.begin()].push_back(a);
            }
            if (can_pass(S, b)) {
                if (uno(S, b)) {
                    return true;
                }
                circle_point[it - c.begin()].push_back(b);
            }
        }
        if (point_circle_tangent(T, *it, a, b)) {
            if (can_pass(T, a)) {
                if (uno(T, a)) {
                    return true;
                }
                circle_point[it - c.begin()].push_back(a);
            }
            if (can_pass(T, b)) {
                if (uno(T, b)) {
                    return true;
                }
                circle_point[it - c.begin()].push_back(b);
            }
        }
    }
    for (int i = 0; i < SZ(c); ++i) {
        for (int j = i + 1; j < SZ(c); ++j) {
            vector<pair<P, P> > res = circle_tangent(c[i], c[j]);
            for (int k = 0; k < SZ(res); ++k) {
                if (can_pass(res[k].first, res[k].second)) {
                    if (uno(res[k].first, res[k].second)) {
                        return true;
                    }
                    circle_point[i].push_back(res[k].first);
                    circle_point[j].push_back(res[k].second);
                }
            }
        }
    }
    for (int i = 0; i < SZ(c); ++i) {
        sort(circle_point[i].begin(), circle_point[i].end());
        circle_point[i].erase(unique(circle_point[i].begin(), circle_point[i].end()), circle_point[i].end());
        for (int j = 0; j + 1 < SZ(circle_point[i]); ++j) {
            if (can_pass_arc(circle_point[i][j], circle_point[i][j + 1], c[i])) {
                if (uno(circle_point[i][j], circle_point[i][j + 1])) {
                    return true;
                }
            }
        }
    }
    return find_father(0) == find_father(1);
}

double solve() {
    double s = 0, t = 1e8;
    while (t - s > 1e-4) {
        double mid = (s + t) / 2;
        if (ok(mid)) {
            s = mid;
        } else {
            t = mid;
        }
    }
    return s;
}

int main() {
    int ca;
    scanf("%d", &ca);
    while (ca--) {
        scanf("%d %d %d %d", &N, &L, &W, &H);
        mtx.clear();
        for (int i = 0; i < N; ++i) {
            int x, y, l, w, h;
            scanf("%d %d %d %d %d", &x, &y, &l, &w, &h);
            mtx.push_back(Mtx(x, x + l, y, y + w, h));
        }
        S.input(), T.input();
        printf("%.2lf\n", solve());
    }
    return 0;
}