結果

問題 No.2436 Min Diff Distance
コンテスト
ユーザー gew1fw
提出日時 2025-06-12 13:30:56
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,737 bytes
コンパイル時間 153 ms
コンパイル使用メモリ 82,344 KB
実行使用メモリ 151,756 KB
最終ジャッジ日時 2025-06-12 13:36:22
合計ジャッジ時間 27,599 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 7 WA * 10 TLE * 6
権限があれば一括ダウンロードができます

ソースコード

diff # 

n = int(input())
points = []
for idx in range(n):
    x, y = map(int, input().split())
    points.append((x, y, idx))

min_dist = [float('inf')] * n

# Define the four sorted lists
sorted_sum = sorted(points, key=lambda p: p[0] + p[1])
sorted_diff = sorted(points, key=lambda p: p[0] - p[1])
sorted_x = sorted(points, key=lambda p: (p[0], p[1]))
sorted_y = sorted(points, key=lambda p: (p[1], p[0]))

def process(sorted_list, min_dist):
    for i in range(len(sorted_list)):
        current = sorted_list[i]
        current_idx = current[2]
        if i > 0:
            prev = sorted_list[i-1]
            dist = abs(current[0] - prev[0]) + abs(current[1] - prev[1])
            if dist < min_dist[current_idx]:
                min_dist[current_idx] = dist
        if i < len(sorted_list) - 1:
            next_p = sorted_list[i+1]
            dist = abs(current[0] - next_p[0]) + abs(current[1] - next_p[1])
            if dist < min_dist[current_idx]:
                min_dist[current_idx] = dist

process(sorted_sum, min_dist)
process(sorted_diff, min_dist)
process(sorted_x, min_dist)
process(sorted_y, min_dist)

# Precompute max_sum, min_sum, max_diff, min_diff
sum_vals = [p[0] + p[1] for p in points]
diff_vals = [p[0] - p[1] for p in points]

max_sum_val = max(sum_vals)
min_sum_val = min(sum_vals)
max_diff_val = max(diff_vals)
min_diff_val = min(diff_vals)

min_p = float('inf')
for p in points:
    x, y, idx = p
    sum_i = x + y
    diff_i = x - y
    current_max = max(
        sum_i - min_sum_val,
        max_sum_val - sum_i,
        diff_i - min_diff_val,
        max_diff_val - diff_i
    )
    current_min = min_dist[idx]
    p_i = abs(current_max - current_min)
    if p_i < min_p:
        min_p = p_i

print(min_p)
0