ball_lzx.cpp

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

#include <iostream>
#include <cmath>
#include <map>
#include <queue>
#include <vector>
using namespace std;

const double eps = 1e-8;

int dcmp(const double &x) {
    return (x > +eps) - (x < -eps);
}

struct point {
    double x, y;
    point() {}
    point(double _x, double _y) : x(_x), y(_y) {}
    point operator-(const point& a) const {
        return point(x - a.x, y - a.y);
    }
    point operator+(const point& a) const {
        return point(x + a.x, y + a.y);
    }
    point operator*(double a) const {
        return point(x * a, y * a);
    }
    bool operator <(const point& a) const {
        return dcmp(x - a.x) < 0 || (dcmp(x - a.x) == 0 && dcmp(y - a.y) < 0);
    }
    bool operator==(const point& a) const {
        return dcmp(x - a.x) == 0 && dcmp(y - a.y) == 0;
    }
    point rotate(double alpha) const {
        return point(x * cos(alpha) - y * sin(alpha), x * sin(alpha) + y * cos(alpha));
    }
    point normal() {
        double l = sqrt(x * x + y * y);
        return point(x / l, y / l);
    }
};

double dmul(const point& a, const point& b, const point& c) {
    return (c.x - a.x) * (b.x - a.x) + (c.y - a.y) * (b.y - a.y);
}

double xmul(const point& a, const point& b, const point& c) {
    return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
}

double len2(const point& p) {
    return p.x * p.x + p.y * p.y;
}

double dist(const point& a, const point& b) {
    return sqrt(len2(b - a));
}

struct rectangle {
    double x0, y0, x1, y1;
    rectangle() {}
    rectangle(double _x0, double _y0, double _x1, double _y1) {
        x0 = _x0, y0 = _y0, x1 = _x1, y1 = _y1;
    }
};

struct hashTable {
    map<point, int> h;
    int& operator[](const point& p) {
        if (h.find(p) != h.end()) return h[p];
        return h[p] = h.size() - 1;
    }
    void clear() {
        h.clear();
    }
};

const int MaxNumber = 10000;
const int MaxN = 64;

vector<rectangle> rect;
vector<point> ball;
vector<double> rad;
vector<point> on_point[4 * MaxN];
point s, t;
int N;
hashTable hash;

int f[MaxNumber];

void initi() {
    rect.clear(), ball.clear(), rad.clear(), hash.clear();
    for (int i = 0; i < MaxNumber; ++i) {
        f[i] = i;
    }
}

int find(int x) {
    int i = x, t = x;
    while (f[i] != i) i = f[i];
    while (f[t] != i) {
        int temp = f[t]; f[t] = i; t = temp;
    }
    return i;
}

void union_point(const point& a, const point& b) {
    int u = hash[a], v = hash[b];
    if (u == v) return ;
    f[find(u)] = find(v);
}

bool in_circle(const point& p, const point& c, double r) {
    return len2(c - p) < r * r - eps;
}

bool in_arc(const point& p, const point& a, const point& b, const point& c) {
    return dcmp(xmul(p, a, b)) < 0;
}

bool in_rectangle(const point& p, const rectangle& m) {
    return p.x > m.x0 + eps && p.x < m.x1 - eps && p.y > m.y0 + eps && p.y < m.y1 - eps;
}

bool in_some(const point& p) {
    for (unsigned int i = 0; i < rect.size(); ++i) {
        if (in_rectangle(p, rect[i])) {
            return true;
        }
    }
    for (unsigned int i = 0; i < ball.size(); ++i) {
        if (in_circle(p, ball[i], rad[i])) {
            return true;
        }
    }
    return false;
}

bool intersects(const point& a, const point& b, const point& c, const point& d) {
    int d0 = dcmp(xmul(a, b, c)), d1 = dcmp(xmul(a, b, d)), d2 = dcmp(xmul(c, d, a)), d3 = dcmp(xmul(c, d, b));
    if ((d0 ^ d1) == -2 && (d2 ^ d3) == -2) return true;
    return false;
}

bool line_rectangle_intersect(const point& a, const point& b, const rectangle& m) {
    if (intersects(a, b, point(m.x0, m.y0), point(m.x1, m.y1))) return true;
    if (intersects(a, b, point(m.x1, m.y0), point(m.x0, m.y1))) return true;
    return false;
}

bool line_circle_intersect(const point& a, const point& b, const point& c, double r) {
    double d = fabs(xmul(a, b, c)) / dist(a, b);
    if (d > r - eps) return false;
    if (dcmp(dmul(a, b, c)) < 0 || dcmp(dmul(b, a, c)) < 0) return false;
    return true;
}

bool line_intersect(const point& a, const point& b) {
    if (in_some(a) || in_some(b)) return true;
    if (a == b) return false;
    for (unsigned int i = 0; i < rect.size(); ++i) {
        if (line_rectangle_intersect(a, b, rect[i])) {
            return true;
        }
    }
    for (unsigned int i = 0; i < ball.size(); ++i) {
        if (line_circle_intersect(a, b, ball[i], rad[i])) {
            return true;
        }
    }
    return false;
}

bool x_intersect(const point& a, const point& b, const point& c, double r, double yy, double x0, double x1) {
    double delta = r * r - (yy - c.y) * (yy - c.y);
    if (delta < 0) return false;
    double xx0 = c.x + sqrt(delta), xx1 = c.x - sqrt(delta);
    if (xx0 > x0 + eps && xx0 < x1 - eps) {
        if (in_arc(point(xx0, yy), a, b, c)) return true;
    }
    if (xx1 > x0 + eps && xx1 < x1 - eps) {
        if (in_arc(point(xx1, yy), a, b, c)) return true;
    }
    return false;
}

bool y_intersect(const point& a, const point& b, const point& c, double r, double xx, double y0, double y1) {
    double delta = r * r - (xx - c.x) * (xx - c.x);
    if (delta < 0) return false;
    double yy0 = c.y + sqrt(delta), yy1 = c.y - sqrt(delta);
    if (yy0 > y0 + eps && yy0 < y1 - eps) {
        if (in_arc(point(xx, yy0), a, b, c)) return true;
    }
    if (yy1 > y0 + eps && yy1 < y1 - eps) {
        if (in_arc(point(xx, yy1), a, b, c)) return true;
    }
    return false;
}

bool arc_rectangle_intersect(const point& a, const point& b, const point& c, double r, const rectangle& m) {
    double x0 = m.x0, y0 = m.y0, x1 = m.x1, y1 = m.y1;
    if (c.x < x0 - r + eps || c.x > x1 + r - eps || c.y < y0 - r + eps || c.y > y1 + r - eps) {
        return false;
    }
    if (line_rectangle_intersect(a, b, m)) {
        return true;
    }
    if (y_intersect(a, b, c, r, x0, y0, y1)) return true;
    if (y_intersect(a, b, c, r, x1, y0, y1)) return true;
    if (x_intersect(a, b, c, r, y0, x0, x1)) return true;
    if (x_intersect(a, b, c, r, y1, x0, x1)) return true;
    return false;
}

void circle_intersect(const point& s, double a, const point& t, double b, vector<point>& it) {
    double d = dist(s, t);
    double alpha = acos((a * a + d * d - b * b) / (2 * a * d));
    point v = (t - s).normal();
    it.push_back(s + v.rotate(+alpha) * a);
    it.push_back(s + v.rotate(-alpha) * a);
}

bool arc_circle_intersect(const point& a, const point& b, const point& c, double r, const point& p, double t) {
    double d = dist(c, p);
    if (d > r + t - eps) return false;
    if (d < fabs(r - t) + eps) return false;
    vector<point> inter;
    circle_intersect(c, r, p, t, inter);
    return in_arc(inter[0], a, b, c) && in_arc(inter[1], a, b, c);
}

bool arc_intersect(const point& a, const point& b, const point& c, double r) {
    if (in_some(a) || in_some(b)) return true;
    if (a == b) return false;
    for (unsigned int i = 0; i < rect.size(); ++i) {
        if (arc_rectangle_intersect(a, b, c, r, rect[i])) return true;
    }
    for (unsigned int i = 0; i < ball.size(); ++i) {
        if (arc_circle_intersect(a, b, c, r, ball[i], rad[i])) return true;
    }
    return false;
}

void point_tangent(const point& p, const point& c, double r, vector<point>& it) {
    double alpha = acos(r / dist(c, p));
    point v = (p - c).normal();
    it.push_back(c + v.rotate(+alpha) * r);
    it.push_back(c + v.rotate(-alpha) * r);
}

void circle_tangent(const point& s, double a, const point& t, double b, vector<point>& it) {
    double d = dist(s, t);
    if (d < fabs(a - b)) return ;
    double alpha = acos((a - b) / d);
    point v = (t - s).normal();
    point left = v.rotate(+alpha);
    it.push_back(s + left * a); it.push_back(t + left * b);
    left = v.rotate(-alpha);
    it.push_back(s + left * a); it.push_back(t + left * b);
    if (d > a + b) {
        double beta = acos((a + b) / d);
        left = v.rotate(+beta);
        it.push_back(s + left * a); it.push_back(t - left * b);
        left = v.rotate(-beta);
        it.push_back(s + left * a); it.push_back(t - left * b);
    }
}

void build_circle() {
    for (unsigned int i = 0; i < ball.size(); ++i) {
        for (unsigned int j = i + 1; j < ball.size(); ++j) {
            vector<point> inter;
            circle_tangent(ball[i], rad[i], ball[j], rad[j], inter);
            if (inter.size() == 0) continue;
            for (int k = 0; k < 4; k += 2) {
                if (!line_intersect(inter[k], inter[k + 1])) {
                    union_point(inter[k], inter[k + 1]);
                    on_point[i].push_back(inter[k]); on_point[j].push_back(inter[k + 1]);
                }
            }
            if (inter.size() == 8) {
                for (int k = 4; k < 8; k += 2) {
                    if (!line_intersect(inter[k], inter[k + 1])) {
                        union_point(inter[k], inter[k + 1]);
                        on_point[i].push_back(inter[k]); on_point[j].push_back(inter[k + 1]);
                    }
                }
            }
        }
    }
}

void build_s_t() {
    if (!line_intersect(s, t)) union_point(s, t);
    for (unsigned int i = 0; i < ball.size(); ++i) {
        vector<point> inter;
        point_tangent(s, ball[i], rad[i], inter);
        if (!line_intersect(s, inter[0])) {
            union_point(s, inter[0]); on_point[i].push_back(inter[0]);
        }
        if (!line_intersect(s, inter[1])) {
            union_point(s, inter[1]); on_point[i].push_back(inter[1]);
        }
        inter.clear();
        point_tangent(t, ball[i], rad[i], inter);
        if (!line_intersect(t, inter[0])) {
            union_point(t, inter[0]); on_point[i].push_back(inter[0]);
        }
        if (!line_intersect(t, inter[1])) {
            union_point(t, inter[1]); on_point[i].push_back(inter[1]);
        }
    }
}

struct cmp {
    point c;
    cmp(const point& _c) : c(_c) {}
    bool operator() (const point& a, const point& b) {
        return dcmp(xmul(c, a, b)) > 0;
    }
};

void build_graph() {
    hash[s] = 0; hash[t] = 1;
    for (unsigned int i = 0; i < ball.size(); ++i) {
        on_point[i].clear();
    }
    build_s_t();
    build_circle();
    for (unsigned int i = 0; i < ball.size(); ++i) {
        sort(on_point[i].begin(), on_point[i].end(), cmp(ball[i]));
        int k = unique(on_point[i].begin(), on_point[i].end()) - on_point[i].begin();
        for (int j = 0; j < k - 1; ++j) {
            point a = on_point[i][j], b = on_point[i][j + 1], c = ball[i];
            if (!arc_intersect(a, b, c, rad[i])) {
                union_point(a, b);
            }
        }
    }
}

struct Tbox {
    int x, y, l, w, h;
};

Tbox box[MaxN];
int length, wide, height;

double calc(double h, double r) {
    if (h >= r) return r;
    return sqrt(r * r - (r - h) * (r - h));
}

bool solve(double r) {
    initi();
    double radius;
    for (int i = 0; i < N; ++i) {
        double x0 = box[i].x, y0 = box[i].y, x1 = box[i].x + box[i].l, y1 = box[i].y + box[i].w;
        radius = calc(box[i].h, r);
        rect.push_back(rectangle(x0 - radius, y0, x1 + radius, y1));
        rect.push_back(rectangle(x0, y0 - radius, x1, y1 + radius));
        rad.push_back(radius);
        ball.push_back(point(x0, y0));
        rad.push_back(radius);
        ball.push_back(point(x1, y0));
        rad.push_back(radius);
        ball.push_back(point(x1, y1));
        rad.push_back(radius);
        ball.push_back(point(x0, y1));
    }
    radius = calc(height, r);
    if (2 * radius > length || 2 * radius > wide) {
        return false;
    }
    rect.push_back(rectangle(0, 0, length - radius, radius));
    rect.push_back(rectangle(length - radius, 0, length, wide - radius));
    rect.push_back(rectangle(radius, wide - radius, length, wide));
    rect.push_back(rectangle(0, radius, radius, wide));
    
    if (in_some(s) || in_some(t)) {
        return false;
    }
    build_graph();
    return find(0) == find(1);
}

int main(void) {
    int x0, y0, x1, y1;
    int T;
    scanf("%d", &T);
    while (T--) {
        scanf("%d", &N);
        scanf("%d%d%d", &length, &wide, &height);
        if (N == 0 && length == 0 && wide == 0 && height == 0) break;
        for (int i = 0; i < N; ++i) {
            scanf("%d%d%d%d%d", &box[i].x, &box[i].y, &box[i].l, &box[i].w, &box[i].h);
        }
        scanf("%d%d%d%d", &x0, &y0, &x1, &y1);
        s = point(x0, y0);
        t = point(x1, y1);
        double l = 0, h = 1e10;
        while (fabs(l - h) > eps) {
            double mid = (l + h) / 2;
            if (solve(mid)) l = mid;
            else h = mid;
        }
        printf("%.2lf\n", l);
    }
    return 0;
}