Rocky Mountain Regional Contest 2015

Start

2015-11-14 17:00 UTC

Rocky Mountain Regional Contest 2015

End

2015-11-14 22:00 UTC
The end is near!
Contest is over.
Not yet started.
Contest is starting in -1600 days 6:27:49

Time elapsed

5:00:00

Time remaining

0:00:00

Problem E
Space Junk

/problems/junk/file/statement/en/img-0001.png
According to NASA’s web page, there are more than $500\, 000$ pieces of “space junk” that are tracked. Care must be taken in mission planning so satellites and other spacecrafts do not collide with these pieces of space junk.

For this problem, we will consider the simplified case in which both the spacecraft and the space junk can be modelled as spheres that are travelling in a straight line. Given the current locations of the two spheres as well as their velocities, when would they collide in the future, if ever?

Input

The first line of input contains a single positive integer $T \leq 500$ indicating the number of test cases. Each test case is specified by two lines. The first line specifies the sphere representing the spacecraft, while the second line specifies the sphere representing the space junk. Each sphere is specified by the seven integers $ x, y, z, r, v_ x, v_ y, v_ z$. The center of the sphere is currently located at $(x,y,z)$, the radius of the sphere is $r$, and the sphere is travelling along the direction specified by the vector $(v_ x,v_ y, v_ z)$. If the vector is $(0,0,0)$, the sphere is stationary.

The absolute value of all integers are at most 100, and $r$ is positive. All coordinates and radii are measured in meters, and the velocities are measured in meters/second.

You may assume that the two spheres do not touch each other initially.

Output

For each test case, output a line containing the time (in seconds) at which the spacecraft first collides with the space junk. If they never collide, print No collision instead. Answers within 0.01 of the correct result are acceptable.

Sample Input 1 Sample Output 1
3
10 3 -10 5 -9 3 -8
2 0 0 6 -4 3 -10
-7 5 0 3 -1 0 3
10 7 -6 6 -2 0 4
-4 -1 0 3 -1 -5 -6
2 1 8 6 4 0 -1
0.492
8.628
No collision