結果

問題 No.2436 Min Diff Distance
コンテスト
ユーザー gew1fw
提出日時 2025-06-12 14:18:30
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,727 bytes
コンパイル時間 375 ms
コンパイル使用メモリ 82,304 KB
実行使用メモリ 183,248 KB
最終ジャッジ日時 2025-06-12 14:18:35
合計ジャッジ時間 4,460 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 3 TLE * 1 -- * 19
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

# Precompute sums and diffs for all points
sums = [x + y for x, y, _ in points]
diffs = [x - y for x, y, _ in points]

max_sum = max(sums)
min_sum = min(sums)
max_diff = max(diffs)
min_diff = min(diffs)

# Compute max_dist for each point
max_dist = [0] * n
for x, y, idx in points:
    s = x + y
    d = x - y
    current_max = max(
        s - min_sum,
        max_sum - s,
        d - min_diff,
        max_diff - d
    )
    max_dist[idx] = current_max

# Initialize min_dist with infinity
min_dist = [float('inf')] * n

# Define the sorted lists
sorted_sum = sorted(points, key=lambda p: (p[0] + p[1], p[0], p[1]))
sorted_diff = sorted(points, key=lambda p: (p[0] - p[1], 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]))

# Process each sorted list to find min distances
for sorted_list in [sorted_sum, sorted_diff, sorted_x, sorted_y]:
    for i in range(len(sorted_list)):
        x, y, idx = sorted_list[i]
        # Check previous neighbor
        if i > 0:
            prev_x, prev_y, prev_idx = sorted_list[i-1]
            d = abs(x - prev_x) + abs(y - prev_y)
            if d < min_dist[idx]:
                min_dist[idx] = d
        # Check next neighbor
        if i < len(sorted_list) - 1:
            next_x, next_y, next_idx = sorted_list[i+1]
            d = abs(x - next_x) + abs(y - next_y)
            if d < min_dist[idx]:
                min_dist[idx] = d

# Compute the minimal P_i
min_p = float('inf')
for i in range(n):
    p = abs(max_dist[i] - min_dist[i])
    if p < min_p:
        min_p = p

print(min_p)
0