LC 100240. 最小化曼哈顿距离

https://leetcode.cn/problems/minimize-manhattan-distances/description/

看了评论才大概知道曼哈顿距离的某些特性距离 - OI Wiki

\begin{align} |xi - xj| + |yi - yj| \\ = max(xi-xj, xj-xi) + max(yi-yj, yj-yi) \\ = max(xi-xj + yi-yj, xi-xj + yj-yi, xj-xi + yi-yj, xj-xi + yj-yi) \\ = max((xi+yi) - (xj + yj), (xi-yi) - (xj-yj), (xj-yj) - (xi-yi), (yj+xj) - (xi+xi))) \\ = max(abs((xi + yi) - (xj + yj)), abs((xi-yi) - (xj - yj))) \end{align}

所以最终我们关心的是(x+y), 以及(x-y)之间的最大差值，这个就是集合中中两点之间最大的曼哈顿距离。

class Solution:
    def minimumDistance(self, points: List[List[int]]) -> int:
        from sortedcontainers import SortedList
        s1, s2 = SortedList(), SortedList()
        for (x, y) in points:
            s1.add(x + y)
            s2.add(x - y)

        ans = 1 << 30
        for (x, y) in points:
            s1.remove(x + y)
            s2.remove(x - y)
            a = s1[-1] - s1[0]
            b = s2[-1] - s2[0]
            ans = min(ans, max(a, b))
            s1.add(x + y)
            s2.add(x - y)
        return ans