1375 - Detonated mines
Time Limit : 2 Second
Memory Limit : 128 MB
Submission: 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