HEISLAZY - He is Lazy

no tags 

Original statement in spanish at http://www.dc.uba.ar/events/icpc/download/problems/taip2011-problems.pdf

As we all know, Humberto is really lazy. He is so lazy that he sticks his nose out of the window so that the wind will blow it for him. Obviously, he hasn't worked at all in his whole life. However, he got lucky and won a lot of money in the lottery. With some of that money he bought an empty field, and made build several houses inside of it, where he moved with his family and friends. Thus, Humberto can go in a straight line from any point in his field to any other, without having to make detours because of urban design (for the sake of simplicity, we consider the objects in Humberto's field as dots, so they don't interfere in Humberto's way).

Sadly, that was not enough for Humberto, so in order to walk even less he decided to have installed some catapults in strategic points of his field. Each catapult can send him from the point where it is installed, to any point at a certain fixed distance (that depends on the range of the catapult).

But, in spite of simplifying his life, the catapults made the task of choosing a way in the field a real headache, because Humberto wants to walk as less as possible. As tired as he is of all his problems, he decided to use the rest of his money to hire you to tell him the minimum distance he has to walk to move from a given point in the field to another.

Input

The input contains several test cases. Each test case is described in several lines. The first line contains five integers N, P_X, P_Y, L_X and L_Y. N represents the number of catapults in the field (1 <= N <= 100). The pair (P_X, P_Y) indicates the coordinates in the XY plane ot the starting point for Humberto, while the pair (L_X, L_Y) indicates analogously the destination point (1 <= P_X, P_Y, L_X, L_Y <= 109). Each of the next N lines describes a different catapult, using three integers C_X, C_Y and F, that indicate the point (C_X, C_Y) where the catapult of strength F is installed. This means that Humberto may move, without walking, from the point (C_X, C_Y) to any point in the plane that is at a distance of exactly F from (C_X, C_Y). Assume that in each test case all the points given in the plane are different. The end of the input is indicated by a single line containing the number -1 five times, and it should not be processed as a test case.

Output

For each test case, output a single line containing a rational number that represents the minimum distance Humberto has to walk in order to get from the starting point to the destination point, using some or none of the catapults. Round the answer to the nearest rational with two decimal digits. In case of a tie, round up. Print exactly two digits after the decimal point, even if that means ending the number with 0's.

Example

Input:

1 10 10 20 10
11 10 9
1 20 10 10 10
11 10 9
2 1 1 12 1
3 1 6
8 1 5
1 12 12 1 1
6 6 9
5 10 10 1 1
3 3 7
8 3 7
8 8 7
3 8 7
5 5 5
-1 -1 -1 -1 -1

Output:

1.00
10.00
4.00
10.41
5.11

hide comments
nadstratosfer: 2021-01-31 16:38:53

Sum(n) < 9000 per test file (less than 200 cases). Not too much, but if you're using slow language, consider various ideas; for me the intuitive algo wouldn't pass in pure Python, but another one got the green bar easily.


Added by:Pablo Ariel Heiber
Date:2011-10-04
Time limit:2.355s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Argentinian Programming Tournament 2011