We are given N line segments on the 2D plane. We want to find the maximum radius of
an empty circle whose center coordinates (xc,yc) are constrained as follows:
* 0 ≤ xc ≤ L
* yc = 0
A circle is empty if no part of a segment is located strictly inside of it (thus, a segment
may touch the circle, but may not intersect with the interior of the circle).
The first line of the input file contains the number of test cases T. The test cases are
described next. The first line of a test case contains the integer numbers N and L (1 ≤ N ≤ 2000
and 0 ≤ L ≤ 10000). The next N lines of the test case contain 4 integers each, describing the
coordinates of the endpoints of a segment: xa, ya, xb and yb. The coordinates of the endpoints of
the segment are (xa,ya) and (xb,yb). All the coordinates are between -20000 and +20000. Every
two consecutive numbers on the same line are separated by a single blank.
For each test case print a line containing a real number R, denoting the maximum radius
of an empty circle whose center obeys the constraints. The number must be printed with 3
decimal digits (the number must be rounded up or down according to the usual rounding rules).
1 4 10 1 1 10 3 5 3 9 1 3 1 4 1 8 3 11 -3
2.118
Migrated from old NTUJ.
SEERC 2010
| No. | Testdata Range | Score |
|---|