Space Junk

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?


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.


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
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
No collision
CPU Time limit 1 second
Memory limit 1024 MB
Difficulty 4.6medium
Statistics Show
License Creative Commons License (cc by-sa)

Please log in to submit a solution to this problem

Log in