Sliding Puzzle

All submissions for this problem are available.
Famous company Strange Puzzles Inc. has designed a brand new series of puzzles aimed at students who are fond of competitive programming. In this problem we are going to consider one of them named "Sliding Windows".
The puzzle consists of an infinite twodimensional plane and n rectangles located in it. Each of the rectangles has its sides parallel to the coordinate axes. The puzzle is considered to be solved if for any two rectangles it is true that at least one of them is covered by the other one. Formally, rectangle i covers rectangle j if and only if for any point of the plane (x, y) which lies inside rectangle j, it also lies inside rectangle i.
The only action that you are allowed to perform is to shift the rectangles up, down, left or right. In one unit of time you can take one of the rectangles and shift it exactly by 1 unit in one of these four directions.
As a true competitive programmer you wonder what the minimum number of time units required to solve the puzzle is (if it can be solved at all).
Input
 The first line of the input contains a single integer T — the number of test cases in the given input. Then follow T descriptions of individual tests.
 The first line of teach testcase contains a single integer, n — the number of rectangles.
 The i^{th} of the next n lines contains four integers l_{i}, b_{i}, r_{i} and u_{i} — this signifies that (l_{i}, b_{i}) is the lower left corner and (r_{i}, u_{i}) is the upper right corner of the i^{th} rectangle.
Output
 If the puzzle can not be solved for the given set of rectangles print 1 in the only line of the output. Otherwise print a single integer equal to the minimum number of time units required to solve the puzzle.
Constraints
 1 ≤ T ≤ 200000
 1 ≤ n ≤ 200000
  10^{9} ≤ l_{i} < r_{i} ≤ 10^{9}
  10^{9} ≤ b_{i} < u_{i} ≤ 10^{9}
 It's guaranteed that the sum of n over all test cases in one test file won't exceed 1000000.
Example
Input: 2 2 0 1 1 2 1 0 2 1 3 0 0 4 1 1 1 1 2 2 1 5 2 Output: 1 4
Explanation
Testase 1: No matter how we move the rectangles, one rectangle cannot cover the other rectangle. Hence the answer is 1.
Testcase 2: One of the optimal solutions is to shift the first rectangle up by 1 unit, second rectangle right by 1 unit and third rectangle left by 2 units. This takes a total of 4 time units and hence that is the answer.
Author:  balajiganapath 
Tags  balajiganapath 
Date Added:  23122017 
Time Limit:  5 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions