Vision

All submissions for this problem are available.
Read problems statements in Mandarin chinese, Russian and Vietnamese as well.
You are given two points $P$ and $Q$ and an opaque sphere in a threedimensional space. The point $P$ is not moving, while $Q$ is moving in a straight line with constant velocity. You are also given a direction vector $d$ with the following meaning: the position of $Q$ at time $t$ is $Q(t) = Q(0) + d \cdot t$, where $Q(0)$ is the initial position of $Q$. It is guaranteed that $Q$ is not visible from $P$ initially (at time $t=0$). It is also guaranteed that $P$ and $Q$ do not touch the sphere at any time. Find the smallest positive time $t_v$ when $Q$ is visible from $P$, i.e. when the line segment connecting points $P$ and $Q$ does not intersect the sphere. ### Input  The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.  The first and only line of each test case contains 13 spaceseparated integers.  The first three integers $P_x, P_y, P_z$ denote the coordinates of $P$.  The next three integers $Q_x, Q_y, Q_z$ denote the initial coordinates of $Q$.  The next three integers $d_x, d_y, d_z$ denote the components of the direction vector $d$.  The last four integers $c_x, c_y, c_z, r$ denote the coordinates of the centre of the sphere and its radius. ### Output For each test case, print a single line containing one real number — the time $t_v$. Your answer will be considered correct if its absolute or relative error does not exceed $10^{6}$. It is guaranteed that $t_v$ exists and does not exceed $10^9$. ### Constraints  $1 \le T \le 10^5$  the absolute values of coordinates of all points do not exceed $2\cdot10^9$  $1 \le r \le 10^9$ ### Subtasks **Subtask #1 (25 points):** $P_z = Q_z = d_z = c_z = 0$ **Subtask #2 (75 points):** original constraints ### Example Input ``` 1 3 0 0 10 10 0 0 10 0 0 3 0 3 ``` ### Example Output ``` 1.0000000000 ```Author:  nots0fast 
Tester:  mgch 
Tags  binarysearch, crossproduct, easymedium, geometry, june18, likecs, nots0fast, nots0fast 
Date Added:  4042018 
Time Limit:  2 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, kotlin, PERL6, TEXT, SCM chicken, CLOJ, COB, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions