问题 4344 --(2008珠海赛) Bomb the Bridge
4344: (2008珠海赛) Bomb the Bridge时间限制: 1 Sec 内存限制: 256 MB
提交: 0 解决: 0
You want to destroy a bridge with bombs. The lower-left corner of the bridge is at (0, 0) and the upper-
right corner is at (w, l). There are already b bombs exploded, the i−th bomb created a hole of radius
ricentering 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 ﬁnite number of points), so that no one can go through
the bridge from y = 0 to y = l.
Your task is to ﬁnd 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 allowd to used 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 ﬁrst 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 ≤ 1000, 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, rounded to nearest integer.
100 100 2
15 50 20
90 50 30
100 100 1
50 50 40
100 100 1
10 50 10