Factory Robot

In a factory hall (size 1000 × 1000 meters) there are a number of circular pillars having various radii. The pillars don’t touch each other or the walls. The company owning the factory is planning to buy a guard robot, which is to move around in the hall. In the four corners of the hall there are machines which the guard robot must be able to reach by zigzagging between the pillars and the walls (the machines themselves are no obstacles). All guard robots available for sale are also circular. Before the company decides which robot to buy, they want to find out the maximum radius size it can have, so that it is still able to reach all four machines. No part of the robot may extend outside the hall. If the robot has radius r, then it must be able to reach the coordinates (r, r), (1000 − r, r), (r, 1000 − r) and (1000 − r, 1000 − r), from where it can reach the four machines. The diameter of the robot must be less than the shortest distance between a pillar and a corner. Input The first line in the input contains the number of test cases (at most 20). Each case starts with a line containing a single integer N, the number of pillars (1 ≤ N ≤ 200). Then follows N lines. Each such line contains three integers x, y and r: the coordinates (x,y) and radius (r) of a pillar (1 < x, y < 999, 1 ≤ r ≤ 499). Output For each test case, output a line containing a single floating point value: the maximum radius of the guard robot. The number should be printed with exactly three decimal digits (rounded correctly). Sample Input 1 3 165 520 110 560 430 30 590 115 75 Sample Output 132.562