The Largest Circle

Time limit5sMemory limit128 MB

Summary
Given N segments, find the maximum radius of a circle centered on the x-axis within [0,L] that touches but never crosses any segment, using binary search plus geometric distance checks.
Level

Hard8 of 10

Topics
Binary search, Geometry, Math
Solved
No attempts yet

Problem

There are NN line segments in the two-dimensional plane. Write a program that finds the radius of the largest "empty" circle satisfying all of the following:

  1. The circle's center is (xc,yc)(x_c, y_c).
  2. 0≤xc≤L0 \le x_c \le L.
  3. yc=0y_c = 0 (that is, the center lies on the xx-axis).

An "empty" circle is one that does not cross any of the given segments. Touching a segment (tangency) is allowed.

Input

The first line contains the number of test cases TT. Each test case has the following form:

  • One line with two integers NN and LL (1≤N≤20001 \le N \le 2000, 0≤L≤100000 \le L \le 10000).
  • The next NN lines each contain four integers xa,ya,xb,ybx_a, y_a, x_b, y_b describing the two endpoints of a segment; that is, the segment's endpoints are (xa,ya)(x_a, y_a) and (xb,yb)(x_b, y_b).

All coordinates are integers between −20000-20000 and 2000020000, inclusive.

Output

For each test case, output on one line the radius of the largest circle, rounded to three digits after the decimal point.

Examples1

  1. Example 1

    Input
    1
4 10
1 1 10 3
5 3 9 1
3 1 4 1
8 3 11 -3
    Expected output
    2.118