Fast and safe
Time Limit : 1 Second
Memory Limit : 128 MB
Submission: 19
Solved: 4
- Description
- In the Game Red Alert, our soviet infantry marches towards enemy base. But the enemies have several Prism Tanks to defend us. Their tanks are so fierce that our soldiers all sacrifice except our commander qiqilrq. Now qiqilrq is going to escape, but what he is faced with is a field full of radar of the enemy. Thanks to the god, qiqilrq has a device that can detect all the radars and their effective area. Even so, he cannot find a path that is fastest and safe(ie. Do not be detected by any radar). Can you help him?
Suppose every radar i is a point in 2D plane, and every point in the plane with distance to it LESS than Ri can be detected by it. Any two radars have distinct positions and may have different detecting distance. You should find the shortest safe path for qiqilrq to escape. For simplicity, just calculate the length of the path.
- Input
- First line: an integer t, denoting number of test cases.
For every case:
First line: an integer n (0<n<60), number of radars
Each of the following n lines: 3 integers xi, y1, ri, indicating the position and the detecting distance of the i-th radar.
Last line: 4 integers X1, Y1, X2, Y2. X1 and Y1 is the coordinate of the current position of qiqilrq; X2 and Y2 is the destination of qiqilrq.
All integers above are in the range of [-10000, 10000].
You can assume the initial point and the destination are both in safe area.
- Output
- If there exists a fastest safe path, output the length of it in one line with a precision of four decimals, otherwise output “God bless qiqilrq” in one line.
- sample input
-
2 2 1 1 1 1 4 1 0 0 2 5 2 -1 0 1 1 0 1 0 -1 0 1
- sample output
-
5.6955 2.0000
- hint
- source
- Isun