Given 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 be the side length of the squares. What is the minimum possible value of such that all the points can be covered?
The standard input will contain 10 datasets. Each dataset begins with an integer . The next lines each contain two integers , , the points in the plane.
For the first 4 cases, .
For each dataset, output the value of .
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