human
I found an interesting problem on https://codeforces.com/problemset/problem/1419/F:
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-----

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-----

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$.

-----Examples-----
Input
4
100 0
0 100
-100 0
0 -100

Output
100
Input
7
0 2
1 0
-3 0
0 -2
-1 -1
-1 -3
-2 -3

Output
-1
Input
5
0 0
0 -1
3 0
-2 0
-2 1

Output
2
Input
5
0 0
2 0
0 -1
-2 0
-2 1

Output
2

-----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...

I tried it in Python, but could not do it. Can you solve it?

 ... Write me a Python program to find such minimal $t$ that it is possible to check each detachment?
assistant
#Here is Python program to find such minimal $t$ that it is possible to check each detachment.

# import numpy as npy
import functools
import math

n=int(input())
x=[0 for i in range(n+2)]
y=[0 for i in range(n+2)]
adj=[[] for i in range(n+2)]
idx=[]
idy=[]
for i in range(n):
    x[i],y[i]=map(int,input().split())
    idx.append(i)
    idy.append(i)

def cmpx(a,b):
    if x[a]!=x[b]:
        if x[a]<x[b]:
            return -1
        else:
            return 1
    if y[a]!=y[b]:
        if y[a]<y[b]:
            return -1
        else:
            return 1
    return 0
    
def cmpy(a,b):
    if y[a]!=y[b]:
        if y[a]<y[b]:
            return -1
        else:
            return 1
    if x[a]!=x[b]:
        if x[a]<x[b]:
            return -1
        else:
            return 1
    return 0

idx=sorted(idx,key=functools.cmp_to_key(cmpx))
idy=sorted(idy,key=functools.cmp_to_key(cmpy))

# print(idx)
# print(idy)

def disx(a,b):
    if x[a]!=x[b]:
        return 1e18
    return y[b]-y[a]
    
def disy(a,b):
    if y[a]!=y[b]:
        return 1e18
    return x[b]-x[a]

l=0
r=2000000000
ans=-1

while l<=r:
    # print(l,r)
    mid=(l+r)//2
    for i in range(n):
        adj[i]=[]
    for i in range(n-1):
        if disx(idx[i],idx[i+1])<=mid:
            adj[idx[i]].append(idx[i+1])
            adj[idx[i+1]].append(idx[i])
            # print(idx[i],idx[i+1])
        if disy(idy[i],idy[i+1])<=mid:
            adj[idy[i]].append(idy[i+1])
            adj[idy[i+1]].append(idy[i])
            # print(idy[i],idy[i+1])
    col=[0 for i in range(n)]
    cur=0
    def dfs(x):
        col[x]=cur
        for i in range(len(adj[x])):
            if col[adj[x][i]]==0:
                dfs(adj[x][i])
    for i in range(n):
        if col[i]==0:
            cur=cur+1
            dfs(i)
    ok=0
    if cur>4:
        ok=0
    if cur==1:
        ok=1
    if cur==2:
        for i in range(n):
            for j in range(i+1,n):
                if (col[i]!=col[j]):
                    d1=abs(x[i]-x[j])
                    d2=abs(y[i]-y[j])
                    if d1==0 or d2==0:
                        if d1+d2<=2*mid:
     ...