2601. BalL

输入格式

The input consists of multiple test cases. The first line of input contains an integer T, which is the number of

test cases.Each test case is on several lines. The first line contains four integers: N, L, W, H, indicating the

number of obstacles; the length, width of the board; and the height of walls.

The coordinate of the lower-left corner is (0,0), the upper-right one is (L, W).

Each of the following N lines consists of five integers: Xi, Yi, Li, Wi, Hi, indicating the coordinate of the

lower-left corner of an obstracle and it’s length, width and height. So the upper-right corner of the obstracle

is (Xi + Li, Yi + Wi).

The last line of a test case consists of four integers: Sx, Sy, Tx, Ty which indicate the coordinates of

start point:(Sx, Sy), and end point:(Tx, Ty).

[Technical Specification]

T is an integer, and T <= 50.

N is an integer, and 0 <= N <=10.

All integers EXCEPT N are in the range [1, 1000].

You can assume those obstracles? sides are parallel to OX, OY and OZ axis, the start point and end point are

rightful(not outside the board or inside an obstracle).

All part of an obstracle is in the board.

The integers on the same line are separated by ONE space.

The test cases are separated by ONE empty line.

NO other spaces or lines will appear in the test data.

输出格式

For each test case, print a single line consists of the radius of the largest ball, rounded to two fractional

digits. Output ‘0.00’(without quotes) if there is no ball can reach its end point from the start point.

4
3 1000 1000 42
102 101 3 2 468
106 104 2 3 335
100 107 4 1 501
101 106 106 100
4 1000 1000 170
108 103 2 3 725
105 109 4 1 479
101 104 1 4 359
103 101 2 2 963
100 100 105 106
2 1000 1000 465
102 100 2 3 706
106 103 2 3 146
100 103 110 103
0 1000 1000 282
100 100 102 102

1.00
1.58
2.00
100.00