1426 -- Seashore
Time Limit :1000 MS Memory Limit :65536 KB
Accepts : 38 Submits : 110
User Accepts : 35 User Submits : 40
<Submit>   <Statistics>   <Discuss>

Description

Arriving at the seashore makes Lucy very happy. However, it is a hot day and the sun shines bright. Lucy doesn’t want to be browned by the sun, so she’d like to stay at hotel. However, Coach Fang asked Frank to find her. Since Lucy didn’t bring the cell phone with him, Frank has to find her by himself. Frank is clever, seeing there are many seashore umbrellas on the seashore, and Lucy always hides under the umbrellas to avoid sunlight.

Since the seashore umbrellas are all round, there may be some overlapping places among them. To avoid the sunlight too, Frank hopes to find the shortest distance under the sun to find Lucy by using these umbrellas. As shown in the picture, the dotted lines show the distance he would walk under the sunlight.

Input

The first line has an integer as the number of test cases.

The format of each test case is as follows:

n

Frank.x Frank.y Lucy.x Lucy.y

circle1.x circle1.y circle1.r

circle2.x circle2.y circle2.r

…….

circlen.x circlen.y circlen.r

n represents the number of beach umbrella (0 < n <= 1000), (Frank.x, Frank.y) means the coordinate Frank locates, and (Lucy.x Lucy.y) means the coordinate Lucy locates.

circlei.x circlei.y circlei.r shows the coordinate and radius of the ith beach umbrella.

Output

The shortest distance Frank has to be under the sunlight to find Lucy, keeping three decimals

Sample Input

2
1
0 2 2 0
0 0 1
2
0 2 2 0
0 0 1
0 1 1

Sample Output

2.000
1.000

Source

Beijing University of Post and Telecommunication Campus Contest 2009
<Submit>   <Statistics>   <Discuss>
 


Powered by Zhang Zhaoning PDL College of Computer
Since 2006.03.09 | 2007.11.22 | 2010.03.02 Copyright (r) 2006 - 2010 All Rights Reserved