1395 -- Rope
Time Limit :1000 MS Memory Limit :65536 KB
Accepts : 13 Submits : 46
User Accepts : 7 User Submits : 12
<Submit>   <Statistics>   <Discuss>

Description

Due to the phone booklet event, zzningxp got the phone numbers of all the ALPCs (top secret?). He was so glad that he sent a challenge manifesto to the excellent ALPC who help to work out that.
A week later, this ALPC received a packet. When he opened the packet with great care, he found that it was a toy and challenge-answer letter.
Actually, the toy is very simple, as shown in the figure below. There are two important points -- start point and end point and several disks which can spin only in one direction, clockwise or anticlockwise. What he has to do is use a rope to coil up all the disks from the start point to the end point. The game is finished when all the disks are spinning when pulling the rope at the end point.
But this ALPC wanted to measure the length of the rope wherever the points and disks are, so he’d like you to design a program for him. He decides the order of the disks and your job is to compute the length of the rope needed.
Note that the rope is so well designed that it can drive the disk once it touches the disk. There is always a continuous contact part between the rope and each disk, sometimes the contact part maybe only a single point.

Input

The first line is an integer N indicating the test cases number.
For each test cases, there are two integers in the first line, start_x and start_y, and two integers in the second line, end_x and end_y, which are the coordinates of the start point and end point and vary in range [-1000,1000].
The next line has only one integer n(0 <= n < 30), which is the number of the disks.
The details of disks are in the following n lines, each line for each disk. In each line, there are four integers: xi, yi, ri and di; xi and yi are the coordinates of the center of the disk, ri (0 < ri < 40) the radius of the disk and di the direction of spinning(0 means clockwise an 1 anticlockwise). 
You can assure that all the disks are not intersected.
 
Note that the order of the disks rolled by the rope is as the same as the order of the input.

Output

For each test case, print a number L with two decimal precision which is the length of rope needed.
It’s guaranteed that when the rope drives the disks, all the disks can be connected by the rope and the rope will not self-intersect.
 

Sample Input

3
0 0
10 0
3
2 0 1 0
5 0 1 0
8 0 1 0
0 1
1 0
3
1 5 1 0
5 5 1 0
5 1 1 0
0 0
4 4
2
4 2 1 1
0 2 1 0

Sample Output

10.51
20.71
19.04

Source

Alpc NUDT 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