結果

問題 No.2436 Min Diff Distance
コンテスト
ユーザー gew1fw
提出日時 2025-06-12 18:43:01
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,738 bytes
コンパイル時間 150 ms
コンパイル使用メモリ 82,192 KB
実行使用メモリ 140,488 KB
最終ジャッジ日時 2025-06-12 18:43:33
合計ジャッジ時間 5,420 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 7 WA * 8 TLE * 8
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

sum_xy = [x + y for x, y in points]
diff_xy = [x - y for x, y in points]

max_sum = max(sum_xy)
min_sum = min(sum_xy)
max_diff = max(diff_xy)
min_diff = min(diff_xy)

max_xy_idx = sum_xy.index(max_sum)
min_xy_idx = sum_xy.index(min_sum)
max_x_y_idx = diff_xy.index(max_diff)
min_x_y_idx = diff_xy.index(min_diff)

max_dist = [0] * n
for i in range(n):
    x_i, y_i = points[i]
    current_max = 0
    for j in [max_xy_idx, min_xy_idx, max_x_y_idx, min_x_y_idx]:
        x_j, y_j = points[j]
        d = abs(x_i - x_j) + abs(y_i - y_j)
        if d > current_max:
            current_max = d
    max_dist[i] = current_max

sorted_xy = sorted(range(n), key=lambda i: (points[i][0] + points[i][1]))
sorted_x_y = sorted(range(n), key=lambda i: (points[i][0] - points[i][1]))
sorted_x = sorted(range(n), key=lambda i: points[i][0])
sorted_y = sorted(range(n), key=lambda i: points[i][1])

pos_xy = [0] * n
for idx, i in enumerate(sorted_xy):
    pos_xy[i] = idx

pos_x_y = [0] * n
for idx, i in enumerate(sorted_x_y):
    pos_x_y[i] = idx

pos_x = [0] * n
for idx, i in enumerate(sorted_x):
    pos_x[i] = idx

pos_y = [0] * n
for idx, i in enumerate(sorted_y):
    pos_y[i] = idx

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

for i in range(n):
    current_min = float('inf')
    x_i, y_i = points[i]
    
    pos = pos_xy[i]
    start = max(0, pos - k)
    end = min(len(sorted_xy) - 1, pos + k)
    for j in sorted_xy[start:end+1]:
        if j == i:
            continue
        x_j, y_j = points[j]
        d = abs(x_i - x_j) + abs(y_i - y_j)
        if d < current_min:
            current_min = d
    
    pos = pos_x_y[i]
    start = max(0, pos - k)
    end = min(len(sorted_x_y) - 1, pos + k)
    for j in sorted_x_y[start:end+1]:
        if j == i:
            continue
        x_j, y_j = points[j]
        d = abs(x_i - x_j) + abs(y_i - y_j)
        if d < current_min:
            current_min = d
    
    pos = pos_x[i]
    start = max(0, pos - k)
    end = min(len(sorted_x) - 1, pos + k)
    for j in sorted_x[start:end+1]:
        if j == i:
            continue
        x_j, y_j = points[j]
        d = abs(x_i - x_j) + abs(y_i - y_j)
        if d < current_min:
            current_min = d
    
    pos = pos_y[i]
    start = max(0, pos - k)
    end = min(len(sorted_y) - 1, pos + k)
    for j in sorted_y[start:end+1]:
        if j == i:
            continue
        x_j, y_j = points[j]
        d = abs(x_i - x_j) + abs(y_i - y_j)
        if d < current_min:
            current_min = d
    
    min_dist[i] = current_min

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