P16293 [Lanquiao Cup 2026 NOI Qualifier Java Group A] Strange Map

Xiao Lan is traveling in a certain country. The cities in this country are arranged on a hexagonal grid, as shown in the figure. Each hexagon in the figure represents a city. :::align{center}  ::: If two cities share a common edge, then Xiao Lan can move from one city to the other in one step. For any two cities, if it takes at least $k$ steps to walk from one city to the other, then the distance between these two cities is defined as $k$. In other words, the distance here is the minimum number of steps between the two cities. Each city can be represented by a unique coordinate $(x, y)$. Its meaning is: starting from the city with coordinate $(0, 0)$, first walk $x$ steps along the $X$ direction, then walk $y$ steps along the $Y$ direction, and you will reach that city. Now you are given the coordinates of $n$ cities. You need to find, among these $n$ cities, the distance between the two cities that are farthest apart.

The first line contains a positive integer $n$, indicating the number of cities given. The next $n$ lines each contain two integers $x_i, y_i$, representing the coordinates of the $i$-th city.

Output one line containing one integer, representing the distance between the two farthest cities among the given $n$ cities.

### Sample Explanation These four cities are exactly the four cities marked in the figure. Among them, the farthest pair of cities is $(-1, -1)$ and $(4, 2)$. Starting from $(-1, -1)$, you can first walk 3 steps in the upper-right direction to reach $(2, 2)$; then walk 2 steps along the positive direction of the $X$ axis to reach $(4, 2)$. The shortest distance between these two cities is 5, so the answer is 5. ### Constraints For $50\%$ of the testdata, $n \le 3000$. For all testdata, $2 \le n \le 3 \times 10^5$, $|x_i|, |y_i| \le 10^9$. Translated by ChatGPT 5