Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Angry Mamu

By battirunner · Limits 1s, 512 MB

We all little brothers of Sohel vai are now gathered in a party at his home. “Mamu”, the most popular figure among us is also invited today. Unfortunately Mamu arrived to the party a little late. In the meantime, the birthday cake was already in everyone’s stomach. Mamu couldn’t take this grief and become quite angry. He went outside immediately. He went to a nearest playground, sat down on a place beside a big pillar and determined not to move.

As we love Mamu very much, we need to reach Mamu and make him join us in the party. Now, you are asked to bring him back. We tell you the coordinate where you should start from and the coordinate where Mamu is sitting right now. But the problem is the huge pillar - the center and radius of which are known. If you cannot reach Mamu due to this pillar then you will first go on a straight line and then you can turn at any angle on any point of the line only once. After that you can again move forward towards the direction you are facing after you turned. You need to calculate the shortest length you need to travel to reach Mamu. You can assume that there is no awkward situation where Mamu or you are inside the pillar.

Input

The first line will contain a single integer: the number of test cases to follow. Every line that follows the first line will contain a single test case with the following seven integers: X1, Y1 (your position), X2, Y2 (Mamu’s position), CX,CY (center of the circular pillar) and R denoting radius of the pillar.

All the inputs will be between -100 ≤ X1, X2, Y1, Y2, CX, CY ≤ 100 and 100 > R > 0.

Output

For each case you need to print the case number and the shortest distance by which you can reach Mamu. You need to print three digits after the decimal point. Follow the sample input output format.

Sample

InputOutput
2
1 1 2 2 3 3 1
5 5 7 7 2 2 2
Case 1: 1.414
Case 2: 2.828

Discussion

Statistics


11% Solution Ratio

bqi343Earliest, Aug '16

AungkurFastest, 0.0s

bqi343Lightest, 131 kB

bqi343Shortest, 1369B

Submit

Login to submit

Related Contests