結果

問題 No.2436 Min Diff Distance
コンテスト
ユーザー lam6er
提出日時 2025-03-20 20:28:48
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 3,303 bytes
コンパイル時間 171 ms
コンパイル使用メモリ 82,712 KB
実行使用メモリ 54,952 KB
最終ジャッジ日時 2025-03-20 20:29:53
合計ジャッジ時間 5,145 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 3 TLE * 1 -- * 19
権限があれば一括ダウンロードができます

ソースコード

diff # 

import bisect

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    n = int(data[0])
    points = []
    idx = 1
    for i in range(n):
        x = int(data[idx])
        y = int(data[idx + 1])
        points.append((x, y, i))
        idx += 2

    # Precompute for max calculations
    list_plus = sorted([(x + y, x, y) for x, y, _ in points], key=lambda x: x[0])
    list_minus = sorted([(x - y, x, y) for x, y, _ in points], key=lambda x: x[0])
    list_x = sorted([(x, y) for x, y, _ in points], key=lambda x: (x[0], x[1]))
    list_y = sorted([(y, x) for x, y, _ in points], key=lambda x: (x[0], x[1]))  # (y, x) and sorted by y then x

    # Precompute max and min for plus and minus
    max_plus = max(p[0] for p in list_plus)
    min_plus = min(p[0] for p in list_plus)
    max_minus = max(p[0] for p in list_minus)
    min_minus = min(p[0] for p in list_minus)

    min_p = float('inf')

    # Function to compute min distance for a given sorted list
    def compute_min_dist(x_i, y_i, sorted_list, key_func, elem_func):
        key = key_func(x_i, y_i)
        search_key = [key]
        if len(sorted_list[0]) > 1:
            search_key += [float('-inf')] * (len(sorted_list[0]) - 1)
        search_key = tuple(search_key)
        pos = bisect.bisect_left(sorted_list, search_key)
        start = max(0, pos - 5)
        end = min(len(sorted_list) - 1, pos + 5)
        min_dist = float('inf')
        for j in range(start, end + 1):
            elem = sorted_list[j]
            x_j, y_j = elem_func(elem)
            if x_j == x_i and y_j == y_i:
                continue
            dist = abs(x_j - x_i) + abs(y_j - y_i)
            if dist < min_dist:
                min_dist = dist
        return min_dist

    for x_i, y_i, _ in points:
        # Compute max_i
        s_plus = x_i + y_i
        s_minus = x_i - y_i
        max_i = max(
            s_plus - min_plus,
            max_plus - s_plus,
            s_minus - min_minus,
            max_minus - s_minus
        )

        # Compute min_i by checking all sorted lists
        min_dist = float('inf')

        # Check list_plus (sorted by x+y)
        def key_plus(x, y): return x + y
        def elem_plus(elem): return (elem[1], elem[2])
        dist = compute_min_dist(x_i, y_i, list_plus, key_plus, elem_plus)
        if dist < min_dist:
            min_dist = dist

        # Check list_minus (sorted by x - y)
        def key_minus(x, y): return x - y
        def elem_minus(elem): return (elem[1], elem[2])
        dist = compute_min_dist(x_i, y_i, list_minus, key_minus, elem_minus)
        if dist < min_dist:
            min_dist = dist

        # Check list_x (sorted by x then y)
        def key_x(x, y): return x
        def elem_x(elem): return (elem[0], elem[1])
        dist = compute_min_dist(x_i, y_i, list_x, key_x, elem_x)
        if dist < min_dist:
            min_dist = dist

        # Check list_y (sorted by y then x)
        def key_y(x, y): return y
        def elem_y(elem): return (elem[1], elem[0])
        dist = compute_min_dist(x_i, y_i, list_y, key_y, elem_y)
        if dist < min_dist:
            min_dist = dist

        p_i = abs(max_i - min_dist)
        if p_i < min_p:
            min_p = p_i

    print(min_p)

if __name__ == "__main__":
    main()
0