Snakes and their Discussions
All submissions for this problem are available.
Read problems statements in Mandarin Chinese, Russian and Vietnamese as well.
There are n snakes in Snakeland. Each snake can be denoted by either a horizontal or a vertical segment in the 2-D grid.
The snakes want to hold a discussion over the benefits and limitations of capitalism. Two snakes can share their ideas with each other if they have at least one cell in common with each other. You want the snakes to have a proper discussion, i.e. each snake should be able to share their ideas with every other snake. In one second, you can move a snake horizontally or vertically by one unit. Also, you can move as many snakes simultaneously as you wish. Find the minimum number of seconds required to make this discussion possible.
The first line of the input contains an integer T denoting number of test cases. The description of the T test cases follows.
The first line of each test case contains an integer n.
Each of the next n lines contains four space separated integers x1, y1, and x2, y2, denoting that the head of the snake is at (x1, y1) and the tail is at (x2, y2). It is guaranteed that snake will be denoted by either a horizontal or vertical segment.
For each test case output a single integer corresponding to the answer of the problem.
- 1 ≤ T ≤ 50
- 1 ≤ n ≤ 50
- 1 ≤ x1, y1, x2, y2 ≤ 50
Input 3 2 1 1 1 3 1 1 3 1 2 1 1 1 3 2 1 3 1 3 1 1 1 3 2 1 3 1 2 2 2 2 Output 0 1 1
Example 1. The snakes have a common cell at coordinates (1, 1). So, they will be able to talk to each other. There is no need to move them.
Example 2. Move the horizontal snake (i.e. 2, 1, 3, 1) to the left by 1 unit. It will now be (1, 1, 2, 1). Now, the first and second snakes will have at least one common cell and will be able to talk to each other. Hence, because you spent one second, the answer is 1.
Example 3. In the first second, move the first snake (i.e. 1, 1, 1, 3) to the right by 1 unit, it will be (2, 1, 2, 3). Also, simultaneously, move the second snake (2, 1, 3, 1) upwards by 1 unit. It will now be at (2, 2, 3, 2). So, after this one second, each pair of snakes have at least one common cell with each other and can talk and have a proper discussion.
|Tags||admin2, basic-math, greedy, proof, snckpb17|
|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, SCALA, 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, PERL6, TEXT, SCM chicken, PYP3, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.