結果

問題 No.2436 Min Diff Distance
ユーザー lam6er
提出日時 2025-04-16 15:30:57
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,631 bytes
コンパイル時間 352 ms
コンパイル使用メモリ 81,920 KB
実行使用メモリ 54,020 KB
最終ジャッジ日時 2025-04-16 15:35:06
合計ジャッジ時間 4,652 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 3 TLE * 1 -- * 19
権限があれば一括ダウンロードができます

ソースコード

diff # 

import bisect

n = int(input())
points = [tuple(map(int, input().split())) for _ in range(n)]

if n == 1:
    print(0)
    exit()

# Precompute global values for max and min Manhattan distances
sums = [x + y for x, y in points]
diffs = [x - y for x, y in points]
max_s = max(sums)
min_s = min(sums)
max_d = max(diffs)
min_d = min(diffs)

# Sort the points in four different ways
sorted_x = sorted(points)
sorted_y = sorted(points, key=lambda p: (p[1], p[0]))
sorted_s = sorted(points, key=lambda p: (p[0] + p[1], p[0], p[1]))
sorted_d = sorted(points, key=lambda p: (p[0] - p[1], p[0], p[1]))

# Create dictionaries to find the index of each point in the sorted lists
def create_pos_dict(sorted_list):
    return {point: idx for idx, point in enumerate(sorted_list)}

pos_x = create_pos_dict(sorted_x)
pos_y = create_pos_dict(sorted_y)
pos_s = create_pos_dict(sorted_s)
pos_d = create_pos_dict(sorted_d)

k = 5  # Number of neighbors to check in each direction
min_p = float('inf')

for x, y in points:
    s = x + y
    d = x - y
    max_i = max(max_s - s, s - min_s, max_d - d, d - min_d)
    current_min = float('inf')
    
    # Check neighbors in sorted_x
    idx = pos_x[(x, y)]
    start = max(0, idx - k)
    end = min(len(sorted_x) - 1, idx + k)
    for i in range(start, end + 1):
        nx, ny = sorted_x[i]
        if nx == x and ny == y:
            continue
        dist = abs(x - nx) + abs(y - ny)
        if dist < current_min:
            current_min = dist
    
    # Check neighbors in sorted_y
    idx = pos_y[(x, y)]
    start = max(0, idx - k)
    end = min(len(sorted_y) - 1, idx + k)
    for i in range(start, end + 1):
        nx, ny = sorted_y[i]
        if nx == x and ny == y:
            continue
        dist = abs(x - nx) + abs(y - ny)
        if dist < current_min:
            current_min = dist
    
    # Check neighbors in sorted_s
    idx = pos_s[(x, y)]
    start = max(0, idx - k)
    end = min(len(sorted_s) - 1, idx + k)
    for i in range(start, end + 1):
        nx, ny = sorted_s[i]
        if nx == x and ny == y:
            continue
        dist = abs(x - nx) + abs(y - ny)
        if dist < current_min:
            current_min = dist
    
    # Check neighbors in sorted_d
    idx = pos_d[(x, y)]
    start = max(0, idx - k)
    end = min(len(sorted_d) - 1, idx + k)
    for i in range(start, end + 1):
        nx, ny = sorted_d[i]
        if nx == x and ny == y:
            continue
        dist = abs(x - nx) + abs(y - ny)
        if dist < current_min:
            current_min = dist
    
    p_i = abs(max_i - current_min)
    if p_i < min_p:
        min_p = p_i

print(min_p)
0