3102. 最小化曼哈顿距离

发表于2024-07-09更新于2024-07-09字数统计1.8k阅读时长19分阅读次数

摘要
Title: 3102. 最小化曼哈顿距离
Categories: 曼哈顿距离、切比雪夫距离

Powered by:NEFU AB-IN

Link

3102. 最小化曼哈顿距离

题意

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

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

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

思路

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

    dM((x1,y1),(x2,y2))=∣x1−x2∣+∣y1−y2∣d_M((x_1, y_1), (x_2, y_2)) = |x_1 - x_2| + |y_1 - y_2|

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

    dC((x1,y1),(x2,y2))=max⁡(∣x1−x2∣,∣y1−y2∣)d_C((x_1, y_1), (x_2, y_2)) = \max(|x_1 - x_2|, |y_1 - y_2|)

  • 转化

    1. 曼哈顿距离可以通过两个新坐标 A=x+yA = x + y 和 B=x−yB = x - y 转换为切比雪夫距离。
    2. 对于两个点 (x1,y1)(x_1, y_1) 和 (x2,y2)(x_2, y_2)，计算新坐标 AA 和 BB 后，曼哈顿距离等于这两个新坐标差值的最大值：
      dM((x1,y1),(x2,y2))=dC((A1,B1),(A2,B2))=max⁡(∣A1−A2∣,∣B1−B2∣)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集合的最大值和最小值，就是对应着原先的坐标系的两个点

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
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]])
使用搜索：谷歌必应百度