Given ~N~ distinct points on a 2D plane, you would like to place three identical, axis-aligned squares on the plane such that every point is either inside or on the border on one of the squares.
Let ~L~ be the side length of the squares. What is the minimum possible value of ~L~ such that all the points can be covered?
The standard input will contain 10 datasets. Each dataset begins with an integer ~N~ ~(4 \le N \le 100\,000)~. The next ~N~ lines each contain two integers ~X~, ~Y~ ~(-10^9 \le X,Y \le 10^9)~, the points in the plane.
For the first 4 cases, ~N \le 30~.
For each dataset, output the value of ~L~.
Sample Input (Two Datasets Shown)
4 1 1 2 2 3 3 4 4 5 1 1 2 1 -2 -1 4 4 -4 -2
Educational Computing Organization of Ontario - statements, test data and other materials can be found at ecoocs.org