結果

問題 No.2436 Min Diff Distance
ユーザー gew1fw
提出日時 2025-06-12 16:09:35
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,674 bytes
コンパイル時間 136 ms
コンパイル使用メモリ 82,756 KB
実行使用メモリ 180,248 KB
最終ジャッジ日時 2025-06-12 16:09:52
合計ジャッジ時間 14,494 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 13 WA * 10
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
import math
from collections import defaultdict

def main():
    input = sys.stdin.read().split()
    idx = 0
    N = int(input[idx])
    idx += 1
    points = []
    for _ in range(N):
        x = int(input[idx])
        y = int(input[idx + 1])
        idx += 2
        points.append((x, y))
    
    u = [x + y for x, y in points]
    v = [x - y for x, y in points]
    u_max = max(u)
    u_min = min(u)
    v_max = max(v)
    v_min = min(v)
    
    max_d = [0] * N
    for i in range(N):
        a_i = u[i]
        b_i = v[i]
        md = max(u_max - a_i, a_i - u_min, v_max - b_i, b_i - v_min)
        max_d[i] = md
    
    grid_size = 100
    grid = defaultdict(list)
    for idx_p, (x, y) in enumerate(points):
        grid_u = x // grid_size
        grid_v = y // grid_size
        grid[(grid_u, grid_v)].append((x, y, idx_p))
    
    min_d = [float('inf')] * N
    for i in range(N):
        x_i, y_i = points[i]
        current_min = float('inf')
        nearby_grids = []
        for du in [-1, 0, 1]:
            for dv in [-1, 0, 1]:
                nearby_grids.append((grid_size * (x_i // grid_size + du), grid_size * (y_i // grid_size + dv)))
        for gx, gy in nearby_grids:
            key = (gx // grid_size, gy // grid_size)
            if key in grid:
                for (x, y, j) in grid[key]:
                    if j == i:
                        continue
                    d = abs(x - x_i) + abs(y - y_i)
                    if d < current_min:
                        current_min = d
        min_d[i] = current_min
    
    P = [abs(max_d[i] - min_d[i]) for i in range(N)]
    print(min(P))

if __name__ == "__main__":
    main()
0