3102. 最小化曼哈顿距离

Powered by:NEFU AB-IN

Link

3102. 最小化曼哈顿距离

题意

给你一个下标从 0 开始的数组 points ，它表示二维平面上一些点的整数坐标，其中 points[i] = [xi, yi] 。

两点之间的距离定义为它们的
曼哈顿距离

请你恰好移除一个点，返回移除后任意两点之间的 最大 距离可能的 最小 值。

思路

• 曼哈顿距离（Manhattan Distance）也称为 L1 距离，是两个点在标准坐标系上的绝对轴距离之和。对于两个点

  $$d_M((x_1,y_1),(x_2,y_2))=|x_1-x_2|+|y_1-y_2|$$

• 切比雪夫距离（Chebyshev Distance）也称为 L∞ 距离，是两个点在任何一个坐标轴方向上的最大距离。对于两个点 $((x_1,y_1))$ 和 $((x_2,y_2))$，切比雪夫距离定义为：

  $$d_C((x_1,y_1),(x_2,y_2))=\max (|x_1-x_2|,|y_1-y_2|)$$

• 转化

  1. 曼哈顿距离可以通过两个新坐标 $A=x+y$ 和 $B=x-y$ 转换为切比雪夫距离。
  2. 对于两个点 $(x_1,y_1)$ 和 $(x_2,y_2)$，计算新坐标 $A$ 和 $B$ 后，曼哈顿距离等于这两个新坐标差值的最大值：
     $d_M((x_1,y_1),(x_2,y_2))=d_C((A_1,B_1),(A_2,B_2))=\max (|A_1-A_2|,|B_1-B_2|)$
  3. 通过将曼哈顿距离转换为切比雪夫距离，可以将点与点的数值之差，转换为最大值的维护
  4. 其实A和B都是对应着(x, y)这个点，A和B都是独立的点，所以求A集合的最大值和最小值，就是对应着原先的坐标系的两个点

代码

import random
from collections import Counter, defaultdict, deque
from datetime import datetime, timedelta
from functools import lru_cache
from heapq import heapify, heappop, heappush, nlargest, nsmallest
from itertools import combinations, compress, permutations, starmap, tee
from math import ceil, fabs, floor, gcd, log, sqrt
from string import ascii_lowercase, ascii_uppercase
from sys import exit, setrecursionlimit, stdin
from typing import Any, Dict, List, Tuple, TypeVar, Union

# Constants
TYPE = TypeVar('TYPE')
N = int(2e5 + 10)  # If using AR, modify accordingly
M = int(20)  # If using AR, modify accordingly
INF = int(2e9)
OFFSET = int(100)

# Set recursion limit
setrecursionlimit(INF)

class Arr:
    array = staticmethod(lambda x=0, size=N: [x] * size)
    array2d = staticmethod(lambda x=0, rows=N, cols=M: [Arr.array(x, cols) for _ in range(rows)])
    graph = staticmethod(lambda size=N: [[] for _ in range(size)])
    @staticmethod
    def to_1_indexed(data: Union[List, str, List[List]]):
        """Adds a zero prefix to the data and returns the modified data and its length."""
        if isinstance(data, list):
            if all(isinstance(item, list) for item in data):  # Check if it's a 2D array
                new_data = [[0] * (len(data[0]) + 1)] + [[0] + row for row in data]
                return new_data, len(new_data) - 1, len(new_data[0]) - 1
            else:
                new_data = [0] + data
                return new_data, len(new_data) - 1
        elif isinstance(data, str):
            new_data = '0' + data
            return new_data, len(new_data) - 1
        else:
            raise TypeError("Input must be a list, a 2D list, or a string")

class Str:
    letter_to_num = staticmethod(lambda x: ord(x.upper()) - 65)  # A -> 0
    num_to_letter = staticmethod(lambda x: ascii_uppercase[x])  # 0 -> A
    removeprefix = staticmethod(lambda s, prefix: s[len(prefix):] if s.startswith(prefix) else s)
    removesuffix = staticmethod(lambda s, suffix: s[:-len(suffix)] if s.endswith(suffix) else s)

class Math:
    max = staticmethod(lambda a, b: a if a > b else b)
    min = staticmethod(lambda a, b: a if a < b else b)

class IO:
    input = staticmethod(lambda: stdin.readline().rstrip("\r\n"))
    read = staticmethod(lambda: map(int, IO.input().split()))
    read_list = staticmethod(lambda: list(IO.read()))


class Std:
    @staticmethod
    def find(container: Union[List[TYPE], str], value: TYPE):
        """Returns the index of value in container or -1 if value is not found."""
        if isinstance(container, list):
            try:
                return container.index(value)
            except ValueError:
                return -1
        elif isinstance(container, str):
            return container.find(value)
        
    @staticmethod
    def pairwise(iterable):
        """Return successive overlapping pairs taken from the input iterable."""
        a, b = tee(iterable)
        next(b, None)
        return zip(a, b)
    
    @staticmethod
    def bisect_left(a, x, key=lambda y: y):
        """The insertion point is the first position where the element is not less than x."""
        left, right = 0, len(a)
        while left < right:
            mid = (left + right) >> 1
            if key(a[mid]) < x:
                left = mid + 1
            else:
                right = mid
        return left

    @staticmethod
    def bisect_right(a, x, key=lambda y: y):
        """The insertion point is the first position where the element is greater than x."""
        left, right = 0, len(a)
        while left < right:
            mid = (left + right) >> 1
            if key(a[mid]) <= x:
                left = mid + 1
            else:
                right = mid
        return left
    
    class SparseTable:
        def __init__(self, data: list, func=lambda x, y: x | y):
            """Initialize the Sparse Table with the given data and function."""
            self.func = func
            self.st = [list(data)]
            i, n = 1, len(self.st[0])
            while 2 * i <= n:
                pre = self.st[-1]
                self.st.append([func(pre[j], pre[j + i]) for j in range(n - 2 * i + 1)])
                i <<= 1

        def query(self, begin: int, end: int):
            """Query the combined result over the interval [begin, end]."""
            lg = (end - begin + 1).bit_length() - 1
            return self.func(self.st[lg][begin], self.st[lg][end - (1 << lg) + 1])
    
    class TrieNode:
        def __init__(self):
            """Initialize children dictionary and cost. The trie tree is a 26-ary tree."""
            self.children = {}
            self.cost = INF

        def add(self, word, cost):
            """Add a word to the trie with the associated cost."""
            node = self
            for c in word:
                if c not in node.children:
                    node.children[c] = Std.TrieNode()
                node = node.children[c]
            node.cost = min(node.cost, cost)

        def search(self, word):
            """Search for prefixes of 'word' in the trie and return their lengths and costs."""
            node = self
            ans = []
            for i, c in enumerate(word):
                if c not in node.children:
                    break
                node = node.children[c]
                if node.cost != INF:
                    ans.append([i + 1, node.cost])  # i + 1 to denote length from start
            return ans

    class StringHash:
        def __init__(self, s: str, mod: int = 1_070_777_777):
            """Initialize the StringHash object with the string, base, and mod."""
            self.s = s
            self.mod = mod
            self.base = random.randint(8 * 10 ** 8, 9 * 10 ** 8)
            self.n = len(s)
            self.pow_base = [1] + Arr.array(0, self.n)  # pow_base[i] = BASE^i
            self.pre_hash = Arr.array(0, self.n + 1)  # pre_hash[i] = hash(s[:i])
            self._compute_hash()

        def _compute_hash(self):
            """Compute the prefix hash values and power of base values for the string."""
            for i, b in enumerate(self.s):
                self.pow_base[i + 1] = self.pow_base[i] * self.base % self.mod
                self.pre_hash[i + 1] = (self.pre_hash[i] * self.base + ord(b)) % self.mod

        def get_sub_hash(self, l: int, r: int) -> int:
            """Get the hash value of the substring s[l:r] """
            return (self.pre_hash[r + 1] - self.pre_hash[l] * self.pow_base[r - l + 1] % self.mod + self.mod) % self.mod

        def get_full_hash(self) -> int:
            """Get the hash value of the full string"""
            return self.pre_hash[self.n]

        def compute_hash(self, word: str) -> int:
            """Compute the hash value of a given word using the object's base and mod."""
            h = 0
            for b in word:
                h = (h * self.base + ord(b)) % self.mod
            return h

# ————————————————————— Division line ——————————————————————

class Solution:
    def minimumDistance(self, points: List[List[int]]) -> int:
        n = len(points)
        A = [x + y for x, y in points]
        B = [x - y for x, y in points]

        A_min_st = Std.SparseTable(A, Math.min)
        A_max_st = Std.SparseTable(A, Math.max)
        B_min_st = Std.SparseTable(B, Math.min)
        B_max_st = Std.SparseTable(B, Math.max)

        def get_max_distance_without_index(index):
            if index == 0:
                min_A = A_min_st.query(index + 1, n - 1)
                max_A = A_max_st.query(index + 1, n - 1)
                min_B = B_min_st.query(index + 1, n - 1)
                max_B = B_max_st.query(index + 1, n - 1)
            elif index == n - 1:
                min_A = A_min_st.query(0, index - 1)
                max_A = A_max_st.query(0, index - 1)
                min_B = B_min_st.query(0, index - 1)
                max_B = B_max_st.query(0, index - 1)
            else:
                min_A = Math.min(A_min_st.query(0, index - 1), A_min_st.query(index + 1, n - 1))
                max_A = Math.max(A_max_st.query(0, index - 1), A_max_st.query(index + 1, n - 1))
                min_B = Math.min(B_min_st.query(0, index - 1), B_min_st.query(index + 1, n - 1))
                max_B = Math.max(B_max_st.query(0, index - 1), B_max_st.query(index + 1, n - 1))
            
            return Math.max(max_A - min_A, max_B - min_B)
        
        result = INF
        
        for i in range(len(points)):
            result = Math.min(result, get_max_distance_without_index(i))

        return result


Solution().minimumDistance([[3,10],[5,15],[10,2],[4,4]])