Problem 2581 Bomb the Bridge
Problem Description
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.
Input
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.
Output
For each test case , print the minimal radius of the last bomb.
Sample Input
3
100 100 2
15 50 20
90 50 30
100 100 1
50 50 40
100 100 1
10 50 10
Sample Output
13
50
40
此题很水
四种情况
1，上下桥面都没被炸开口
此种情况 炸弹最小半径为桥宽
2，只有上桥面被炸开口
将与上桥面开口圆有交点的圆视为一个整体，找出这个整体最下面的点，向下桥面作垂线即为直径
3，只有下桥面被炸开口
做法同2
4，上下桥面都被炸开
将与上桥面开口圆有交点的圆视为一个整体a；将与下桥面开口圆有交点的圆视为一个整体b
分别从a，b中任取一圆记下两圆圆心距减去半径和（最小相切圆直径）Ci 最后记下c = min（C1，C2，C3，。。。）
找出整体a最下面的点，向下桥面作垂线记为d
找出整体b最上面的点，向上桥面作垂线记为e
结果即为min（c，d，e）
