Clocks

문제

During the past few years Tim E. has been collecting circle-shaped clocks and he exposed them on a big wall in his living room. He wants to buy another big clock, but because his wall is almost full he wants to know what the radius of the biggest clock is that could be exposed on the wall without overlapping any other clock.

The wall is modelled as a rectangle with width W and height H. For each clock the coordinates (x_i, y_i) of the centre-point and the radius ri are given. The clocks will not overlap with the boundaries of the wall, nor will two clocks overlap, however they might touch each other.

입력

The first line of the input contains a single number: the number of test cases to follow. Each test case has the following format:

• One line with two integers W and H satisfying 1 ≤ W,H ≤ 1,000,000: the width and the height of the wall, respectively.
• One line with an integer C satisfying 0 ≤ C ≤ 50: the number of clocks.
• C lines, each with three integers xi, yi and ri satisfying r_i > 0, 0 ≤ x_i − r_i, x_i + r_i ≤ W, 0 ≤ y_i − r_i and y_i + r_i ≤ H: the location and radius of an existing clock. 

Integers on the same line are separated by single spaces. For any pair of clocks i and j (i ≠ j), (x_i − x_j)² + (y_i − y_j)² ≥ (r_i + r_j)².

출력

For every test case in the input, the output should contain a single real number, on a single line: the maximum radius of a clock that fits on the wall without overlapping with any existing clock or the boundaries of the wall.

Your answer should have either an absolute or a relative error of at most 10⁻⁶. Make sure that you print enough decimals. In particular, if you program in C++, do not use plain cout << M << endl; to output your answer (a double) M, because this sometimes produces too few decimals. Instead, you may use printf ("%lf\n", M); .

1
10 10
4
2 2 1
2 8 1
8 2 1
8 8 1

3.242640687119285