4 4 s 128 MB
A long and straight corridor is ﬁtted with a number of sensors. Each sensor has a certain range within which it can detect objects or persons. If a part of an object is within the sensor’s range, an alarm will go off. Otherwise, nothing will happen.
Ethan needs to traverse this corridor in order to do some spy stuff at the other end. The question is, can he pass through the corridor without being detected? Can he ﬁt so easily that he can bring some equipment along, or does he have to wear some tight clothing? Or can he perhaps sent a robot through instead?
We model the corridor as being two-dimensional (we ignore the height), bounded by two straight lines. Each sensor is located inside the corridor or on a wall. Their scopes are well in between the two ends of the corridor. We model the person or robot going through as a circle. Given the layout, what is the maximum radius this circle can have so that it is possible to negotiate the corridor without being detected?
A visual representation of the samples.
On the ﬁrst line one positive number: the number of test cases, at most 100. After that per test case:
one line with a single integer w (1 ≤ w ≤ 100,000): the width of the corridor. The two walls are given by the lines x = 0 and x = w.
one line with a single integer n (0 ≤ n ≤ 1,000): the number of sensors in the corridor.
n lines with three space-separated integers x, y and r (0 ≤ x ≤ w, -100,000 ≤ y ≤ 100,000 and 1 ≤ r ≤ 100,000): the location and the range of each sensor, respectively.
The two ends of the corridor are at y = -∞ and y = +∞, or in less technical terms, they are far beyond the scope of all the sensors.
Per test case:
one line with one ﬂoating point number: the radius of the largest circular object (or person) that could pass through the corridor without being detected, assuming the object can (be) move(d) with absolute precision. If nothing could possibly get through, the output should be zero. The answer should be rounded to five digits after the decimal point. See the below sample output.
3 10 2 2 0 3 7 12 4 10 2 2 0 3 7 8 4 10 2 2 0 3 7 4 4
1.50000 1.21699 0.00000