Rain of Fire
Contest: Codeforces Round 671 (Div. 2)
Difficulty rating: 2800
Tags: binary search, data structures, dfs and similar, dsu, graphs, implementation

There are $$$n$$$ detachments on the surface, numbered from $$$1$$$ to $$$n$$$, the $$$i$$$-th detachment is placed in a point with coordinates $$$(x_i, y_i)$$$. All detachments are placed in different points.

Brimstone should visit each detachment at least once. You can choose the detachment where Brimstone starts.

To move from one detachment to another he should first choose one of four directions of movement (up, right, left or down) and then start moving with the constant speed of one unit interval in a second until he comes to a detachment. After he reaches an arbitrary detachment, he can repeat the same process.

Each $$$t$$$ seconds an orbital strike covers the whole surface, so at that moment Brimstone should be in a point where some detachment is located. He can stay with any detachment as long as needed.

Brimstone is a good commander, that's why he can create at most one detachment and place it in any empty point with integer coordinates he wants before his trip. Keep in mind that Brimstone will need to visit this detachment, too.

Help Brimstone and find such minimal $$$t$$$ that it is possible to check each detachment. If there is no such $$$t$$$ report about it.

Input format:
The first line contains a single integer $$$n$$$ $$$(2 \le n \le 1000)$$$ — the number of detachments.

In each of the next $$$n$$$ lines there is a pair of integers $$$x_i$$$, $$$y_i$$$ $$$(|x_i|, |y_i| \le 10^9)$$$ — the coordinates of $$$i$$$-th detachment.

It is guaranteed that all points are different.

Output format:
Output such minimal integer $$$t$$$ that it is possible to check all the detachments adding at most one new detachment.

If there is no such $$$t$$$, print $$$-1$$$.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
In the first test it is possible to place a detachment in $$$(0, 0)$$$, so that it is possible to check all the detachments for $$$t = 100$$$. It can be proven that it is impossible to check all detachments for $$$t < 100$$$; thus the answer is $$$100$$$.

In the second test, there is no such $$$t$$$ that it is possible to check all detachments, even with adding at most one new detachment, so the answer is $$$-1$$$.

In the third test, it is possible to place a detachment in $$$(1, 0)$$$, so that Brimstone can check all the detachments for $$$t = 2$$$. It can be proven that it is the minimal such $$$t$$$.

In the fourth test, there is no need to add any detachments, because the answer will not get better ($$$t = 2$$$). It can be proven that it is the minimal such $$$t$$$.

Example input:
4
100 0
0 100
-100 0
0 -100

Example output:
100

Example input:
7
0 2
1 0
-3 0
0 -2
-1 -1
-1 -3
-2 -3

Example output:
-1

Editorial:
We can consider a graph where vertices are the points (detachments), and there is an edge between two points, if it's possible to move from one point to another. It is possible if these points are on the same line ($$$x_i = x_j$$$ or $$$y_i = y_j$$$) and the distance between them is $$$\le T$$$.
Now we can check, whether current $$$t$$$ value is good (whether it is possible to check all detachments). It is easy to see, that it is only possible, when the graph is connected. This means, that we can make a binary search for $$$t$$$. Let's now learn how to check, whether it is possible to add at most one point to make the graph connected.
If there is $$$1$$$ component, then the graph is already connected.
If there are $$$2$$$ components, then we can search through all such pairs of points, that one point is from the first component, and another point is from the second component. We can connect these points, if they are on one line, and the distance between them is $$$\le 2T$$$ or the differences $$$|x_1 - x_2| \le T$$$ and $$$y_1 - y_2 \le T$$$.
If $$$3$$$ are three components, then we should consider triples of points. Two of these points should be on the same line. The added point should be on a segment between these two points, and there are $$$O(n)$$$ such segments. Now let's search through all such pairs (segment, point) and check whether it is possible to place a point on the segment and connect it with the point from the pair.
If there are $$$4$$$ components, then you can search trough pairs (segment, segment), so that one segment is horizontal and another one is vertical (they should make a cross). Now we just need to check whether it is possible to connect their intersection point with all 4 endpoints of the segments.
If there are more, than $$$4$$$ components, then it is not possible to connect them adding only one point, because there are 4 movement directions. If your binary search did not find the answer even for $$$T = 2 \cdot 10^9$$$, then the answer is $$$-1$$$, because the maximal distance between any two points is $$$\le 2 \cdot 10^9$$$.