HUST Monthly 2010.06.13

From: 2010-06-13 12:00:00 To: 2010-06-13 17:00:00 Now: 2017-09-20 01:03:30 Status: Public

G - Detonated mines

Time Limit: 2s Memory Limit: 128MB

Submissions: 313 Solved: 62
Description
In the middle of last century, almighty TianChao placed N mines in a region of Korea. Suppose the region was a plane, the i-th mine was placed at (xi, yi). When the i-th mine exploded, it would trigger off the explosion of other mines with Euclidean distance not larger than than Li from it. In this peaceful age, Korea plans to remove all the mines in this region. Since mine-cleaning is very dangerous, Korea decides to explode one of these mines, to trigger off all the other mines automatically. If the i-th mine triggers off the j-th, and the j-th triggers off the k-th, then the j-th mine is 1-explosion and the k-th mine is 2-explosion. Suppose for the i-th mine, it is Ei-explosion, which mine should they explode to make the maximum value of Ei minimum. You should only tell this minimum value.
Input
Multiple cases. For each case: Fist line contains an integer N(1 <= N <= 300). Following N lines, each contains three integers: xi, yi, Li(0 <= xi, yi, Li <= 1000), indicating the coordinate and the explosion radius of the i-th mine.
Output
Only one line: The minimum value of the max{Ei}. If it can't be done by explode only one mine, out put -1 instead.
Sample Input
2
0 0 1
2 0 3
Sample Output
1
Hint
Source
Hust Monthly 10.06.13/Fei LIU