ball_felicia.cpp

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

    double lab = sqrt(l2ab);
    double l2ap = l2ab - sqr(r);
    double lam = l2ap / lab;
    point v = (b - a) / lab;
    point m = a + (v * lam);
    double lmp = sqrt(l2ap) * r / lab;

    point cand = m + v.turn_left() * lmp;
    if (ok_point(cand, ib) && ok_seg(a, cand)) {
        cand.id = cnt_pt++;
        t1.push_back(cand);
        tangent.push_back(make_pair(a.id, cand.id));
    }
    cand = m - v.turn_left() * lmp;
    if (ok_point(cand, ib) && ok_seg(a, cand)) {
        cand.id = cnt_pt++;
        t1.push_back(cand);
        tangent.push_back(make_pair(a.id, cand.id));
    }
}

void push(int &cnt_pt, point &canda, point &candb, const int &ia, const int &ib, vector <point> &t1, vector <point> &t2, vector <pair <int, int> > &tangent) {
    if (ok_point(canda, ia) && ok_point(candb, ib) && ok_seg(canda, candb)) {
        canda.id = cnt_pt++;
        candb.id = cnt_pt++;
        t1.push_back(canda);
        t2.push_back(candb);
        tangent.push_back(make_pair(canda.id, candb.id));
    }
}

void tangent_circle_circle(int &cnt_pt, const circle &ca, const circle &cb,
        vector <point> &t1, vector <point> &t2, vector <pair <int, int> > &tangent, const int &ia, const int &ib) {
    
    int ret;

    point a = ca.o;
    point b = cb.o;
    double ra = ca.r;
    double rb = cb.r;
    
    double dr = ra - rb;

    if (sgn(dist(a, b) - (ra + rb)) > 0)
        ret = 4;
    else if (sgn(dist(a, b) - dr) > 0)
        ret = 2;
    else
        ret = 0;

    if (ret == 0)
        return;

    double l = dist(a, b);
    double cos_t = dr / l;
    point v = b - a;
    point canda, candb;
    
    //first tangent
    canda = a + v.tolen(ra).turn_left(cos_t);
    candb = b + v.tolen(rb).turn_left(cos_t);
    push(cnt_pt, canda, candb, ia, ib, t1, t2, tangent);
    
    //second tangent
    canda = a + v.tolen(ra).turn_right(cos_t);
    candb = b + v.tolen(rb).turn_right(cos_t);
    push(cnt_pt, canda, candb, ia, ib, t1, t2, tangent);

    if (ret == 2)
        return;

    dr = ra + rb;
    cos_t = dr / l;
    point w = a - b;
     
    //third tangent
    canda = a + v.tolen(ra).turn_left(cos_t);
    candb = b + w.tolen(rb).turn_left(cos_t);
    push(cnt_pt, canda, candb, ia, ib, t1, t2, tangent);

    //forth tangent
    canda = a + v.tolen(ra).turn_right(cos_t);
    candb = b + w.tolen(rb).turn_right(cos_t);
    push(cnt_pt, canda, candb, ia, ib, t1, t2, tangent);  
}

void get_rect_ex() {
    rect_ex.clear();
    for (int i = 0; i < n; i++) {
        rect_ex.push_back(rt(rect[i].xmin - r[i], rect[i].ymin, rect[i].xmax + r[i], rect[i].ymax));
        rect_ex.push_back(rt(rect[i].xmin, rect[i].ymin - r[i], rect[i].xmax, rect[i].ymax + r[i]));
    }
    
}

void get_point_and_tangent(int &cnt_pt) {
    tangent.clear();
    for (int i = 0; i < 4 * n; i++) {
        pt[i].clear();
        pt[i].reserve(80 * n);
    }

    if (ok_seg(ps, pe))
        tangent.push_back(make_pair(ps.id, pe.id));

    for (int i = 0; i < n; i++)
        for (int ii = 0; ii < 4; ii++) {
            int ti = i * 4 + ii;
            if (!point_in_circle(ps, circle(rect[i].p[ii], r[i]))) {
                tangent_point_circle(cnt_pt, ps, circle(rect[i].p[ii], r[i]), pt[ti], tangent, -1, ti);
            }
            if (!point_in_circle(pe, circle(rect[i].p[ii], r[i]))) {
                tangent_point_circle(cnt_pt, pe, circle(rect[i].p[ii], r[i]), pt[ti], tangent, -1, ti);
            }
        }
    if (SZ(tangent) == 0)
        return;

    for (int i = 0; i < 4 * n; i++)
        for (int j = i + 1; j < 4 * n; j++)
            tangent_circle_circle(cnt_pt, circle(rect[i / 4].p[i % 4], r[i / 4]),
                    circle(rect[j / 4].p[j % 4], r[j / 4]), pt[i], pt[j], tangent, i, j);
}

#define maxn 50010
typedef double weight;

class graph_c {
public:
	void init(int _n);
	void dijkstra(int S);
	void add_edge(int u, int v, weight w);
	weight dist[maxn];
	int pa[maxn];
private:
	int n;
	vector <int> r[maxn];
	vector <weight> e[maxn];
	multimap <weight, int> h;
};

void graph_c::init(int _n) {
	n = _n;
	for (int i = 0; i < n; i++) {
		r[i].clear();
		e[i].clear();
	}
}

void graph_c::add_edge(int u, int v, weight w) {
	r[u].push_back(v);
	e[u].push_back(w);
}

void graph_c::dijkstra(int S) {
	weight d, tmp;
	int v;
	multimap<weight, int>::iterator it;
	h.clear();
	for (int i = 0; i < n; i++) dist[i] = -1;
	dist[S] = 0;
	pa[S] = -1;
	h.insert(multimap<weight, int>::value_type(0, S));
	while (!h.empty()) {
		it = h.begin();
		v = it->second;
		d = it->first;
		h.erase(it);
		for (int i = 0; i < SZ(r[v]); i++) {
			tmp = d + e[v][i];
			int j = r[v][i];
			if (dist[j] < 0 || tmp < dist[j]) {
				dist[j] = tmp;
				pa[j] = v;
				h.insert(multimap<weight, int>::value_type(tmp, j));
			}
		}
	}
}

graph_c g;

double get_angle(const point &a, const point &b) {
    if (sgn(cross(a, b)) == 0)
        return 0;
    return acos(dot(a, b) / a.len() / b.len());
}

bool exist_path(double ball_r) {
//    printf("call exist_path(%lf)\n", ball_r);
    r.clear();
    for (int i = 0; i < n; i++) {
        if (sgn(ball_r - h[i]) <= 0)
            r.push_back(ball_r);
        else
            r.push_back(sqrt(sqr(ball_r) - sqr(ball_r - h[i])));
    }

    get_rect_ex();

    ps.id = 0;
    pe.id = 1;

    int cnt_pt = 2;
    get_point_and_tangent(cnt_pt);

    g.init(cnt_pt);

    for (vector <pair <int, int> >::iterator it = tangent.begin(); it != tangent.end(); ++it) {
        g.add_edge(it->first, it->second, 1);
        g.add_edge(it->second, it->first, 1);
    }

    int cnt_arc = 0;

    for (int i = 0; i < 4 * n; i++) {
        for (int j = 0; j < SZ(pt[i]); j++) {
            for (int k = j + 1; k < SZ(pt[i]); k++) {
                point va = pt[i][j] - rect[i / 4].p[i % 4];
                point vb = pt[i][k] - rect[i / 4].p[i % 4];
                if (sgn(cross(va, vb)) > 0) {
                    point t = pt[i][j];
                    pt[i][j] = pt[i][k];
                    pt[i][k] = t;
                }
            }
        }
        for (int j = 0; j + 1 < SZ(pt[i]); j++) {
            int k = j + 1;
            if (ok_arc(arc(rect[i / 4].p[i % 4], pt[i][j], pt[i][k]))) {
                cnt_arc++;
                g.add_edge(pt[i][j].id, pt[i][k].id, 1);
                g.add_edge(pt[i][k].id, pt[i][j].id, 1);
            }
        }
    }
    g.dijkstra(0);
    return g.dist[1] != -1;
}

double max_r() {
    double l = 0, r = 1000000, mid;
    double ret = -1;

//    debug = true;
//    exist_path(400);

    debug = false;
    while (r - l > 1e-3) {
        mid = (l + r) / 2;
        if (exist_path(mid)) {
            l = mid;
            ret = l;
        }
        else {
            r = mid;
        }
    }
//    debug = true;
//    exist_path(ret);
    return ret;
}

int ll, ww, hh;

int main() {
//    mp_begin();
    int ca;
    scanf("%d", &ca);
    while (ca--) {
        scanf("%d%d%d%d", &n, &ll, &ww, &hh);
        rect.clear();
        h.clear();
        
        rect.push_back(rt(-1, 0, 0, ww));
        h.push_back(hh);

        rect.push_back(rt(0, -1, ll, 0));
        h.push_back(hh);

        rect.push_back(rt(ll, 0, ll + 1, ww));
        h.push_back(hh);

        rect.push_back(rt(0, ww, ll, ww + 1));
        h.push_back(hh);
        for (int i = 0; i < n; i++) {
            int x, y, l, w, _h;
            scanf("%d%d%d%d%d", &x, &y, &l, &w, &_h);
            rect.push_back(rt(x, y, x + l, y + w));
            h.push_back(_h);
        }
        int ax, ay, bx, by;
        scanf("%d%d%d%d", &ax, &ay, &bx, &by);
        ps = point(ax, ay);
        pe = point(bx, by);

        n += 4;
        double ret = max_r();
        if (ret == -1)
            ret = 0;
        printf("%.2lf\n", ret);
    }
//    mp_end();
    return 0;
}