Bomb the Bridge

You want to destroy a bridge with bombs .The lower-left corner of the bridge is at (0,0) and upper-right corner is at ( w , l ). There are already b bombs exploded , the i-th bombcreated a hole of radius ri centering at (xi , yi) .You want to throw exactly one more bomb so that the bridge is split into two connected parts( though the two parts can share a finite number of points),so that no one can go through the bridge from y=0 to y=l .You task is to find the minimal radius of the last bomb to split the bridge , assuming that the last bomb can explode precisely at the position you want (possibly at non-integer
coordinates).Note that you are only allowed to use bombs with integer radius .That is ,even if a bomb with radius 1.01 is sufficient , you have to use a bomb with radius 2, since you only have bombs with integer radius.

The first line contains t (1<= t <=10), the number of test cases followed . Each test case begins with three integers w , l, b (1<= w , l<=100 , 0<= b <= 10). Each of the following b lines contains three integers integers xi, yi , ri (0<= x <=w, 0<= y <=l, 0< r <=100). The bridge is guaranteed to be connected before the last bomb.

For each test case , print the minimal radius of the last bomb.

3
100 100 2
15 50 20
90 50 30 
100 100 1
50 50 40
100 100 1
10 50 10

13 
50 
40

ECJTU 2009 Spring Contest