結果

問題 No.2436 Min Diff Distance
ユーザー lam6er
提出日時 2025-04-16 15:39:25
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,129 bytes
コンパイル時間 618 ms
コンパイル使用メモリ 81,968 KB
実行使用メモリ 126,484 KB
最終ジャッジ日時 2025-04-16 15:44:58
合計ジャッジ時間 20,291 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 7 WA * 16
権限があれば一括ダウンロードができます

ソースコード

diff # 

n = int(input())
points = []
s = []
d = []
for _ in range(n):
    x, y = map(int, input().split())
    points.append((x, y))
    s_val = x + y
    d_val = x - y
    s.append(s_val)
    d.append(d_val)

# Prepare sorted_s and sorted_d arrays along with their positions
sorted_s = sorted((s[i], i) for i in range(n))
sorted_d = sorted((d[i], i) for i in range(n))

pos_in_s = [0] * n
for idx in range(n):
    _, original_i = sorted_s[idx]
    pos_in_s[original_i] = idx

pos_in_d = [0] * n
for idx in range(n):
    _, original_i = sorted_d[idx]
    pos_in_d[original_i] = idx

min_s = sorted_s[0][0]
max_s = sorted_s[-1][0]
min_d = sorted_d[0][0]
max_d = sorted_d[-1][0]

global_min_P = float('inf')
k = 5  # Number of neighbors to check on each side

for i in range(n):
    current_s = s[i]
    current_d = d[i]
    
    # Calculate max_distance
    max_s_val = max(current_s - min_s, max_s - current_s)
    max_d_val = max(current_d - min_d, max_d - current_d)
    max_distance = max(max_s_val, max_d_val)
    
    # Calculate min_distance
    min_distance = float('inf')
    
    # Check neighbors in sorted_s
    pos = pos_in_s[i]
    start = max(0, pos - k)
    end = min(n - 1, pos + k)
    for j in range(start, end + 1):
        s_j, original_j = sorted_s[j]
        if original_j == i:
            continue
        d_j = d[original_j]
        current_dist = max(abs(current_s - s_j), abs(current_d - d_j))
        if current_dist < min_distance:
            min_distance = current_dist
    
    # Check neighbors in sorted_d
    pos = pos_in_d[i]
    start = max(0, pos - k)
    end = min(n - 1, pos + k)
    for j in range(start, end + 1):
        d_j, original_j = sorted_d[j]
        if original_j == i:
            continue
        s_j = s[original_j]
        current_dist = max(abs(current_s - s_j), abs(current_d - d_j))
        if current_dist < min_distance:
            min_distance = current_dist
    
    # Calculate P_i and update global_min_P
    if min_distance != float('inf'):
        P_i = abs(max_distance - min_distance)
        if P_i < global_min_P:
            global_min_P = P_i

print(global_min_P)
0