Minimize Maximum Edge in Tree House MST

You are given n tree houses on a 2D plane with their coordinates. Your task is to connect all tree houses using edges weighted by the Manhattan distance. Among all possible spanning trees, you should select the one that minimizes the maximum edge weight, i.e. the maximum Manhattan distance used in the tree is as small as possible.

The Manhattan distance between two points \( (x_1, y_1) \) and \( (x_2, y_2) \) is defined as \( |x_1 - x_2| + |y_1 - y_2| \). This problem can be solved by constructing a Minimum Spanning Tree (MST) using Kruskal's algorithm with a union-find (disjoint set union) data structure. The answer is the maximum edge weight that is included in this MST.

inputFormat

The first line contains an integer n (n ≥ 2), representing the number of tree houses.

The following n lines each contain two space-separated integers x and y, which denote the coordinates of a tree house.

outputFormat

Output a single integer which is the minimized maximum edge weight in the MST of the given tree houses using Manhattan distance.

Recall the Manhattan distance between points \( (x_1, y_1) \) and \( (x_2, y_2) \) is computed as \( |x_1 - x_2| + |y_1 - y_2| \).

4
0 0
2 2
2 0
0 2

2