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 2-D plane. You can travel from a special point (xi, yi) to another special point (xj, yj) if and only if |xi - xj| + |yi - yj| ≥ 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.
- 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 i-th of the next N lines contains two integers, xi and yi, which denotes that (xi, yi) is a special point.
For each test case, output a single line containing the answer.
SubtasksSubtask #1 (20 points):
- 2 ≤ N ≤ 103
- 2 ≤ Sum of N over all test cases ≤ 103
- 2 ≤ N ≤ 3 * 104
- 2 ≤ Sum of N over all test cases ≤ 3 * 104
- Original constraints
- 1 ≤ T ≤ 50
- 2 ≤ N ≤106
- 0 ≤ xi, yi ≤ 109
- 2 ≤ Sum of N over all test cases ≤ 106
Input: 1 6 1 7 8 5 6 3 10 3 5 2 6 10 Output: 9
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.
|Tags||arpa, binary-search, ltime50|
|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, PYP3, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.