P2218 [HAOI2007] Covering Problem

Someone planted $N$ saplings on a mountain. Winter has come, the temperature dropped sharply, and the saplings are too fragile. The owner wants to cover them with some plastic sheets. After careful consideration, he decides to use $3$ square plastic sheets of size $L \times L$ to cover the saplings. We set up a 2D Cartesian coordinate system on the mountain; the coordinates of the $i$-th sapling are $(X_i, Y_i)$. The $3$ squares of size $L \times L$ must be axis-aligned. A point lying on the boundary of a square is also considered covered. Of course, we want the plastic area to be as small as possible; that is, find the minimal $L$.

The first line contains an integer $N$. The next $N$ lines each contain two integers $X_i, Y_i$, giving the coordinates of the $i$-th tree. It is guaranteed that no two trees share the same coordinates.

Output one line: the minimal value of $L$.

For $100\%$ of the testdata, $-1,000,000,000 \le X_i, Y_i \le 1,000,000,000$. For $30\%$ of the testdata, $N \le 100$. For $50\%$ of the testdata, $N \le 2000$. For $100\%$ of the testdata, $N \le 20000$. Translated by ChatGPT 5