found\(A(x_1, y_1), B(x_2, y_2)\)。
Euclidean distance
General model: find the shortest geometric distance from one point to another on a coordinate system.
Manhattan Distance
General model: the shortest distance from one point towards another in a grid map.
Chepyshev distance
General model: the distance from one point on a chessboard or in a diagram to eight other neighboring points is 1.
Interconversion of Manhattan and Chepyshev distances
Manhattan borough of New York City\(\to\) Chepyshev:\((x, y) \to (x + y, x - y)\)。
Chepishev (name)\(\to\) Manhattan:\((x, y) \to (\frac{x + y}{2}, \frac{x - y}{2})\)。
The latter is used more often and the Chepyshev distance is taken in the calculation of the\(max\)that are often not very well optimized.
Example: TJOI2013 Squirrel Party - Luogu
After fixing the meeting point, it is straightforward to calculate the distance and is\(O(n)\) The, unacceptable.
We translate into Manhattan distance and find\(x, y\) The contributions are separate and independent, and we can sort, prefix and optimize, and bisect lookups separately. This makes it possible to do a single\(O(2logn)\) Calculations can be made to pass this question.