Practice on Toph

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

The Multiplayer Action Game

Limits: 4s, 512 MB

Have you played the game Agar.io? According to wikipedia, Agar.io is a massively multiplayer action game created by Matheus Valadares. Players control a cell in a map representing a petri dish; the goal is to gain as much mass as possible by swallowing smaller cells without being swallowed by bigger ones.

Now we are going to play the n-dimensional simplified version of it. For simplicity, you will be given the initial position, radius and velocity of an n-dimensional cell of spherical shape in n-dimensional space and a total time limit of 105 seconds to play the game. You have to find whether one cell will eat another cell within the given time limit. If a cell eats up another cell, then you have to find the time when this takes place. Condition for one cell to eat up another one is to cover one cell completely by another one (one must be bigger than the other). Please note that, velocity is a vector quantity. For example, if your initial position is (0,0,0) in 3D space and your velocity is (1,2,-1), then your co-ordinates after 1 second will be (1,2,-1) and after 2 seconds it will be (2,4,-2).

Input

The first line of the input is an integer T (0 < T < 105), denoting the number of test cases. Each test case starts with 3 integers n (1 < n < 11), r1, r2 (0 < r1, r2 ≤ 104) representing the number of dimensions, radius of the first cell and radius of second cell respectively. Then the next two lines represent the initial position of the two cells, each line with n integers representing the positions in vector field. The next two lines contain n integers, each representing the velocity of the first cell and the velocity of the second cell respectively.

Output

For each case, print the desired answer. If one cell doesn’t eat the other one in given time limit, then print -1. Error less than 10-4 is ignored.

Samples

InputOutput
2
2 2 1
0 0
10 10
1 1
-1 -1
3 5 3
0 100 200
200 100 0
10 1 -10
-10 1 10
4.64644661
9.92928932

Author
Discussion
Submit

Login to submit