Travel to all Points

All submissions for this problem are available.
Read problems statements in mandarin chinese, russian and vietnamese as well.
There are N special points on the 2D plane. You can travel from a special point (x_{i}, y_{i}) to another special point (x_{j}, y_{j}) if and only if x_{i}  x_{j} + y_{i}  y_{j} ≥ D.
You need to find the largest integer D, such that we can start at some special point and visit each of the other special points, directly or through other special points. Note that you can visit a special point more than once.
Input
 The first line of the input contains an integer T, denoting the number of test cases. The description of each testcase follows.
 The first line of each testcase contains a single integer, N, which denotes the number of special points.
 The ith of the next N lines contains two integers, x_{i} and y_{i}, which denotes that (x_{i}, y_{i}) is a special point.
Output
For each test case, output a single line containing the answer.
Subtasks
Subtask #1 (20 points): 2 ≤ N ≤ 10^{3}
 2 ≤ Sum of N over all test cases ≤ 10^{3}
 2 ≤ N ≤ 3 * 10^{4}
 2 ≤ Sum of N over all test cases ≤ 3 * 10^{4}
 Original constraints
Constraints
 1 ≤ T ≤ 50
 2 ≤ N ≤10^{6}
 0 ≤ x_{i}, y_{i} ≤ 10^{9}
 2 ≤ Sum of N over all test cases ≤ 10^{6}
Example
Input: 1 6 1 7 8 5 6 3 10 3 5 2 6 10 Output: 9
Explanation
We can start at some point and travel to all of the points if D ≤ 9, but not if D is greater than 9. Hence the answer is 9.
Let us take an example when D is 9. You can start at (1, 7) and move to (8, 5) because 1  8 + 7  5 = 9 ≥ 9. From (8, 5) you can move back to (1, 7) and then to (10, 3). From there you can go to (6, 10) and then to (5, 2). You then go to (1, 7) and then to (6, 3). Hence, we have visited all the special points.
Author:  arpa 
Editorial  https://discuss.codechef.com/problems/TRAVELAL 
Tags  arpa, binarysearch, ltime50 
Date Added:  28072017 
Time Limit:  2 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.5, 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, 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. 