ball_by_momodi.java

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

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;

public class Ball {
	static Scanner cin = new Scanner(System.in);
	final static double eps = 1e-9;

	static int sgn(double a) {
		if (a > eps) {
			return 1;
		}
		if (a < -eps) {
			return -1;
		}
		return 0;
	}

	static double sqr(double a) {
		return a * a;
	}

	static class P implements Comparable<P> {
		double x, y;

		P(double _x, double _y) {
			x = _x;
			y = _y;
		}

		P() {
		}

		boolean equals(P a) {
			return sgn(x - a.x) == 0 && sgn(y - a.y) == 0;
		}

		boolean notEquals(P a) {
			return sgn(x - a.x) != 0 || sgn(y - a.y) != 0;
		}

		P add(P a) {
			return new P(x + a.x, y + a.y);
		}

		P subtract(P a) {
			return new P(x - a.x, y - a.y);
		}

		P multiply(double a) {
			return new P(x * a, y * a);
		}

		P divide(double a) {
			return new P(x / a, y / a);
		}

		P trunc(double a) {
			a /= Math.sqrt(x * x + y * y);
			return new P(x * a, y * a);
		}

		P turnLeft() {
			return new P(-y, x);
		}

		P turnRight() {
			return new P(y, -x);
		}

		void input() {
			x = cin.nextDouble();
			y = cin.nextDouble();
		}

		void output() {
			System.out.printf("%.9f %.9f\n", x, y);
		}

		@Override
		public int compareTo(P b) {
			// TODO Auto-generated method stub
			if (sgn(x - b.x) < 0 || sgn(x - b.x) == 0 && sgn(y - b.y) < 0) {
				return -1;
			}
			if (sgn(x - b.x) == 0 && sgn(y - b.y) == 0) {
				return 0;
			}
			return 1;
		}
	}

	static double cross(P a, P b, P c) {
		return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
	}

	static double dmul(P a, P b, P c) {
		return (b.x - a.x) * (c.x - a.x) + (b.y - a.y) * (c.y - a.y);
	}

	static double dist(P a, P b) {
		return Math.sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
	}

	static double pointLineDist(P a, P S, P T) {
		return Math.abs(cross(a, S, T)) / dist(S, T);
	}

	static P S, T;
	static int N, L, W, H;

	static class Mtx {
		double minx, maxx, miny, maxy, h;

		Mtx(double _minx, double _maxx, double _miny, double _maxy) {
			minx = _minx;
			maxx = _maxx;
			miny = _miny;
			maxy = _maxy;
			gen();
		}

		Mtx(double _minx, double _maxx, double _miny, double _maxy, double _h) {
			minx = _minx;
			maxx = _maxx;
			miny = _miny;
			maxy = _maxy;
			h = _h;
			gen();
		}

		Mtx() {
		}

		P[] d;

		void gen() {
			d = new P[5];
			d[0] = new P(minx, miny);
			d[1] = new P(minx, maxy);
			d[2] = new P(maxx, maxy);
			d[3] = new P(maxx, miny);
			d[4] = d[0];
		}

		P at(int index) {
			return d[index];
		}
	}

	static boolean inRange(double a, double s, double t) {
		return sgn(a - s) > 0 && sgn(a - t) < 0;
	}

	static boolean inMtx(P a, Mtx m) {
		return inRange(a.x, m.minx, m.maxx) && inRange(a.y, m.miny, m.maxy);
	}

	static class C {
		P mid;
		double r;

		C(P _mid, double _r) {
			mid = _mid;
			r = _r;
		}

		C() {
		}

		boolean in(C a) {
			return sgn(r + dist(mid, a.mid) - a.r) < 0;
		}

		boolean equals(C a) {
			return mid.equals(a.mid) && sgn(r - a.r) == 0;
		}

		boolean notEquals(C a) {
			return mid.notEquals(a.mid) || sgn(r - a.r) != 0;
		}

		void output() {
			System.out.printf("%f %f %f\n", mid.x, mid.y, r);
		}
	}

	static List<Mtx> mtx;
	static List<Mtx> m;
	static List<C> c;
	static List<Integer> conca, concb;
	static int[] f;

	static int findFather(int v) {
		if (v != f[v]) {
			return f[v] = findFather(f[v]);
		}
		return v;
	}

	static boolean onCircle(P a, C cir) {
		return sgn(dist(a, cir.mid) - cir.r) == 0;
	}

	static boolean inCircle(P a, C cir) {
		return sgn(dist(a, cir.mid) - cir.r) < 0;
	}

	static boolean inSegment(P a, P S, P T) {
		return sgn(dmul(a, S, T)) < 0;
	}

	static boolean lineCircleCross(P S, P T, C cir, P[] a) {
		double dd = pointLineDist(cir.mid, S, T);
		if (sgn(dd - cir.r) >= 0) {
			return false;
		}
		double ll = Math.sqrt(Math.abs(sqr(cir.r) - sqr(dd)));
		P p;
		if (sgn(cross(S, T, cir.mid)) < 0) {
			p = T.subtract(S).turnLeft().trunc(dd);
		} else {
			p = T.subtract(S).turnRight().trunc(dd);
		}
		a[0] = cir.mid.add(p).add(T.subtract(S).trunc(ll));
		a[1] = cir.mid.add(p).add(S.subtract(T).trunc(ll));
		return true;
	}

	static boolean segmentCircleCross(P S, P T, C cir) {
		P[] a = new P[2];
		if (lineCircleCross(S, T, cir, a)) {
			if (inSegment(a[0], S, T) || inSegment(a[1], S, T)
					|| inSegment(a[0].add(a[1]).divide(2), S, T)) {
				return true;
			}
		}
		return false;
	}

	static boolean segmentSross(P a, P b, P c, P d) {
		double s1 = cross(a, b, c);
		double s2 = cross(a, b, d);
		if (sgn(s2 - s1) == 0) {
			return false;
		}
		P ans = (c.multiply(s2)).subtract(d.multiply(s1)).divide(s2 - s1);
		return inSegment(ans, a, b) && inSegment(ans, c, d);
	}

	static boolean segmentMtxCross(P S, P T, Mtx mm) {
		for (int i = 0; i < 4; ++i) {
			if (segmentSross(S, T, mm.at(i), mm.at(i + 1))) {
				return true;
			}
		}
		return false;
	}

	static boolean canPass(P S, P T) {
		for (int i = 0; i < c.size(); ++i) {
			if (inCircle(S, c.get(i)) || inCircle(T, c.get(i))
					|| segmentCircleCross(S, T, c.get(i))) {
				return false;
			}
		}
		for (int i = 0; i < m.size(); ++i) {
			if (inMtx(S, m.get(i)) || inMtx(T, m.get(i))
					|| segmentMtxCross(S, T, m.get(i))) {
				return false;
			}
		}
		return true;
	}

	static boolean inArc(P p, P S, P T, 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));
	}

	static P midArc(P S, P T, C cir) {
		return cir.mid.add(S.add(T).divide(2).subtract(cir.mid).trunc(cir.r));
	}

	static boolean circleCross(C c1, C c2, P[] a) {
		double len = dist(c1.mid, c2.mid);
		if (sgn(len - c1.r - c2.r) >= 0) {
			return false;
		}
		double x = (len + (sqr(c1.r) - sqr(c2.r)) / len) / 2;
		double t = Math.sqrt(Math.abs(sqr(c1.r) - x * x));
		P p = c2.mid.subtract(c1.mid);
		a[0] = c1.mid.add(p.trunc(x)).add(p.turnLeft().trunc(t));
		a[1] = c1.mid.add(p.trunc(x)).add(p.turnRight().trunc(t));
		return true;
	}

	static boolean arcCircleCross(P S, P T, C cir, C c2) {
		if (cir.in(c2)) {
			return true;
		}
		if (c2.in(cir) || cir.equals(c2)) {
			return false;
		}
		P[] a = new P[2];
		if (circleCross(cir, c2, a)) {
			if (inArc(a[0], S, T, cir) || inArc(a[1], S, T, cir)
					|| inCircle(midArc(S, T, cir), c2)) {
				return true;
			}
		}
		return false;
	}

	static boolean arcSegmentCross(P S, P T, C cir, P segmentS, P segmentT) {
		P[] a = new P[2];
		if (lineCircleCross(segmentS, segmentT, cir, a)) {
			if ((inSegment(a[0], segmentS, segmentT) && inArc(a[0], S, T, cir))
					|| (inSegment(a[1], segmentS, segmentT) && inArc(a[1], S,
							T, cir))) {
				return true;
			}
		}
		return false;
	}

	static boolean arcMtxCross(P S, P T, C cir, Mtx mm) {
		for (int i = 0; i < 4; ++i) {
			if (arcSegmentCross(S, T, cir, mm.at(i), mm.at(i + 1))) {
				return true;
			}
		}
		return false;
	}

	static boolean canPassArc(P a, P b, C cir) {
		for (int i = 0; i < c.size(); ++i) {
			if (cir.notEquals(c.get(i)) && arcCircleCross(a, b, cir, c.get(i))) {
				return false;
			}
		}
		for (int i = 0; i < m.size(); ++i) {
			if (arcMtxCross(a, b, cir, m.get(i))) {
				return false;
			}
		}
		return true;
	}

	static double findr(double h, double r) {
		if (sgn(h - r) >= 0) {
			return r;
		} else {
			return Math.sqrt(Math.abs(r * r - (r - h) * (r - h)));
		}
	}

	static boolean pointCircleTangent(P p, C cir, P[] a) {
		double len = dist(p, cir.mid);
		if (sgn(len - cir.r) <= 0) {
			return false;
		}
		double x = Math.sqrt(Math.abs(len * len - cir.r * cir.r));
		double h = x * cir.r / len;
		double y = Math.sqrt(Math.abs(x * x - h * h));
		a[0] = p.add(cir.mid.subtract(p).trunc(y)).add(
				cir.mid.subtract(p).turnLeft().trunc(h));
		a[1] = p.add(cir.mid.subtract(p).trunc(y)).add(
				cir.mid.subtract(p).turnRight().trunc(h));
		return true;
	}

	static List<Pair<P, P>> circleTangent(C a, C b) {
		List<Pair<P, P>> ans = new ArrayList<Pair<P, P>>();
		double len = dist(a.mid, b.mid);
		if (sgn(len - a.r - b.r) > 0) {
			double x = len * a.r / (b.r + a.r);
			double y = len * b.r / (a.r + b.r);
			double ta = Math.sqrt(Math.abs(sqr(x) - sqr(a.r)));
			double ha = a.r * ta / x;
			double pa = Math.sqrt(Math.abs(sqr(a.r) - sqr(ha)));
			double tb = Math.sqrt(Math.abs(sqr(y) - sqr(b.r)));
			double hb = b.r * tb / y;
			double pb = Math.sqrt(Math.abs(sqr(b.r) - sqr(hb)));
			P ab = b.mid.subtract(a.mid);
			P ba = a.mid.subtract(b.mid);
			ans.add(new Pair<P, P>(a.mid.add(ab.trunc(pa)).add(
					ab.turnRight().trunc(ha)), b.mid.add(ba.trunc(pb)).add(
					ba.turnRight().trunc(hb))));
			ans.add(new Pair<P, P>(a.mid.add(ab.trunc(pa)).add(
					ab.turnLeft().trunc(ha)), b.mid.add(ba.trunc(pb)).add(
					ba.turnLeft().trunc(hb))));
		}
		if (!a.in(b) && !b.in(a) && a.notEquals(b)) {
			double n = Math.sqrt(Math.abs(sqr(len) - sqr(a.r - b.r)));
			double ha = a.r * n / len;
			double hb = b.r * n / len;
			double pa = Math.sqrt(Math.abs(sqr(a.r) - sqr(ha)));
			double pb = Math.sqrt(Math.abs(sqr(b.r) - sqr(hb)));
			P p = (a.r > b.r ? b.mid.subtract(a.mid) : a.mid.subtract(b.mid));
			ans.add(new Pair<P, P>(a.mid.add(p.trunc(pa)).add(
					p.turnRight().trunc(ha)), b.mid.add(p.trunc(pb)).add(
					p.turnRight().trunc(hb))));
			ans.add(new Pair<P, P>(a.mid.add(p.trunc(pa)).add(
					p.turnLeft().trunc(ha)), b.mid.add(p.trunc(pb)).add(
					p.turnLeft().trunc(hb))));
		}
		return ans;
	}

	static List<P> ID;

	static int findID(P a) {
		for (int i = 0; i < ID.size(); ++i) {
			if (ID.get(i).equals(a)) {
				return i;
			}
		}
		ID.add(a);
		return ID.size() - 1;
	}

	static class Pair<S, T> {
		Pair(S a, T b) {
			first = a;
			second = b;
		}

		S first;
		T second;
	}

	static List<Pair<Integer, Integer>> conc;
	static List<List<P>> circlePoint;

	static boolean ok(double R) {
		m = new ArrayList<Mtx>();
		c = new ArrayList<C>();
		for (Mtx it : mtx) {
			double r = findr(it.h, R);
			m.add(new Mtx(it.minx, it.maxx, it.miny - r, it.maxy + r));
			m.add(new Mtx(it.minx - r, it.maxx + r, it.miny, it.maxy));
			c.add(new C(it.at(0), r));
			c.add(new C(it.at(1), r));
			c.add(new C(it.at(2), r));
			c.add(new C(it.at(3), r));
		}
		{
			double r = findr(H, R);
			m.add(new Mtx(0, L, 0, r));
			m.add(new Mtx(0, L, W - r, W));
			m.add(new Mtx(0, r, 0, W));
			m.add(new Mtx(L - r, L, 0, W));
		}
		if (canPass(S, T)) {
			return true;
		}
		ID = new ArrayList<P>();
		ID.add(S);
		ID.add(T);
		conc = new ArrayList<Pair<Integer, Integer>>();
		circlePoint = new ArrayList<List<P>>(c.size());
		for (int i = 0; i < c.size(); ++i) {
			circlePoint.add(new ArrayList<P>());
		}
		for (int i = 0; i < c.size(); ++i) {
			if (onCircle(S, c.get(i))) {
				circlePoint.get(i).add(S);
			}
			if (onCircle(T, c.get(i))) {
				circlePoint.get(i).add(T);
			}
			P[] a = new P[2];
			if (pointCircleTangent(S, c.get(i), a)) {
				if (canPass(S, a[0])) {
					conc
							.add(new Pair<Integer, Integer>(findID(S),
									findID(a[0])));
					circlePoint.get(i).add(a[0]);
				}
				if (canPass(S, a[1])) {
					conc
							.add(new Pair<Integer, Integer>(findID(S),
									findID(a[1])));
					circlePoint.get(i).add(a[1]);
				}
			}
			if (pointCircleTangent(T, c.get(i), a)) {
				if (canPass(T, a[0])) {
					conc
							.add(new Pair<Integer, Integer>(findID(T),
									findID(a[0])));
					circlePoint.get(i).add(a[0]);
				}
				if (canPass(T, a[1])) {
					conc
							.add(new Pair<Integer, Integer>(findID(T),
									findID(a[1])));
					circlePoint.get(i).add(a[1]);
				}
			}
		}
		for (int i = 0; i < c.size(); ++i) {
			for (int j = i + 1; j < c.size(); ++j) {
				List<Pair<P, P>> res = circleTangent(c.get(i), c.get(j));
				for (int k = 0; k < res.size(); ++k) {
					if (canPass(res.get(k).first, res.get(k).second)) {
						conc.add(new Pair<Integer, Integer>(
								findID(res.get(k).first),
								findID(res.get(k).second)));
						circlePoint.get(i).add(res.get(k).first);
						circlePoint.get(j).add(res.get(k).second);
					}
				}
			}
		}
		for (int i = 0; i < c.size(); ++i) {
			Collections.sort(circlePoint.get(i));
			for (int j = 0; j + 1 < circlePoint.get(i).size(); ++j) {
				if (circlePoint.get(i).get(j).notEquals(
						circlePoint.get(i).get(j + 1))
						&& canPassArc(circlePoint.get(i).get(j), circlePoint
								.get(i).get(j + 1), c.get(i))) {
					conc.add(new Pair<Integer, Integer>(findID(circlePoint.get(
							i).get(j)), findID(circlePoint.get(i).get(j + 1))));
				}
			}
		}
		int len = ID.size();
		f = new int[len];
		for (int i = 0; i < len; ++i) {
			f[i] = i;
		}
		for (int i = 0; i < conc.size(); ++i) {
			int fa = findFather(conc.get(i).first);
			int fb = findFather(conc.get(i).second);
			f[fa] = fb;
			if (findFather(0) == findFather(1)) {
				return true;
			}
		}
		return findFather(0) == findFather(1);
	}

	static 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;
	}

	/**
	 * @param args
	 * 
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int ca = cin.nextInt();
		while (ca-- > 0) {
			N = cin.nextInt();
			L = cin.nextInt();
			W = cin.nextInt();
			H = cin.nextInt();
			if (N == 0 && L == 0 && W == 0 && H == 0) {
				break;
			}
			mtx = new ArrayList<Mtx>();
			for (int i = 0; i < N; ++i) {
				double x = cin.nextDouble();
				double y = cin.nextDouble();
				double l = cin.nextDouble();
				double w = cin.nextDouble();
				double h = cin.nextDouble();
				mtx.add(new Mtx(x, x + l, y, y + w, h));
			}
			S = new P();
			S.input();
			T = new P();
			T.input();
			System.out.printf("%.2f\n", solve());
		}
	}
}