Run Direction

All submissions for this problem are available.
Read problem statement in Mandarin chinese and Vietnamese.
Suzumo is the coach of the ChefLand OI team. Physical condition is very important in any olympiad, so he wants to make the children run a bit as a warmup. The team consists of $N$ children numbered $1$ through $N$ standing at some positions on the $x$axis. For each valid $i$, the initial $x$coordinate of the $i$th kid is $x_i$, the running velocity of the $i$th kid is constant and equal to $v_i$. Suzumo wants to assign a running direction (left or right, i.e. in the direction of decreasing or increasing $x$coordinate) to each kid; the children start running at time $0$ in the assigned directions. Afterwards, Suzumo will measure the smallest time $t$ at which some kid passes another one. Help Suzumo compute the maximum time $t$ if he can assign the directions arbitrarily! **Note:** Child $i$ *passes* child $j$ at time $t_{ij}$ if their coordinates satisfy $x_i < x_j$ at any time $t < t_{ij}$ and $x_i > x_j$ at any time $t > t_{ij}$, or if they satisfy $x_i > x_j$ at any time $t < t_{ij}$ and $x_i < x_j$ at any time $t > t_{ij}$. ### 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 line of each test case contains a single integer $N$.  $N$ lines follow. For each valid $i$, the $i$th of these lines contains two spaceseparated integers $x_i$ and $v_i$. ### Output For each test case, print a single line containing one real number — the maximum possible time $t$, or $1$ if it is possible to assign directions in such a way that no kid ever passes another. Your answer will be considered correct if it has an absolute or relative error less than or equal to $10^{6}$. ### Constraints  $1 \le T \le 100$  $1 \le N \le 50$  $1 \le x_i, v_i \le 10^9$ for each valid $i$  no two children have the same initial positions ### Example Input ``` 1 3 10 10 20 30 30 10 ``` ### Example Output ``` 0.5 ``` ### Explanation **Example case 1:** One optimal assignment of directions is left, right, right.Author:  alei 
Tags  alei, binarysearch, cook93, easymedium, greedy 
Date Added:  15042018 
Time Limit:  1 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
HELP
If you are still having problems, see a sample solution here. 