Manhattan Pairing#11814
For a pair of points on the Cartesian plane (x_1, y_1) and (x_2, y_2), we define the Manhattan distance between them as |x_1-x_2|+|y_1-y_2|. For example, for the pair of points and , the Manhattan distance between them is |4-2|+|1-7| = 2+6 = 8.
You are given 2 \cdot n points on the Cartesian plane, whose coordinates are integers. All -coordinates of the given points are either or .
Split the given points into pairs such that each of these points belongs to exactly one pair, and the maximum Manhattan distance between the points of one pair is minimized.
The first line contains a single integer (1 \le n \le 10^5).
In the following 2 \cdot n lines, each line contains two integers x_i and y_i (0 \le x_i \le 10^9, 0 \le y_i \le 1) — the coordinates of the corresponding point.
Output a single integer — the maximum Manhattan distance between the points of one pair in the optimal partition.
Example 1
Example 2
Example 3
In the second example, the pairing [(18, 0), (14, 0)], [(3, 0), (1, 0)], and [(8, 0), (10, 0)] is the only optimal partition. The Manhattan distances between the points of one pair in this partition are , , and , respectively.
In the third example, the pairing [(0, 1), (2, 1)], [(2, 1), (3, 0)], [(3, 0), (5, 0)], and [(5, 1), (6, 0)] is an optimal partition. All Manhattan distances between the points of one pair in this partition are equal to .
Illustration for the third example
( points): n = 1;
( points): x_i = 0 for 1 \le i \le 2\cdot n;
( points): n \le 4;
( points): n \le 10;
( points): y_i = 0 for 1 \le i \le 2\cdot n;
( points): x_i \neq x_j for 1 \le i < j \le 2\cdot n;
( points): n \le 1000;
( points): no additional restrictions.