結果

問題 No.2436 Min Diff Distance
ユーザー lam6er
提出日時 2025-04-16 00:27:15
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,065 bytes
コンパイル時間 168 ms
コンパイル使用メモリ 81,404 KB
実行使用メモリ 132,048 KB
最終ジャッジ日時 2025-04-16 00:29:07
合計ジャッジ時間 19,511 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 7 WA * 16
権限があれば一括ダウンロードができます

ソースコード

diff # 

def main():
    import sys
    input = sys.stdin.read().split()
    idx = 0
    N = int(input[idx])
    idx += 1
    points = []
    for i in range(N):
        x = int(input[idx])
        y = int(input[idx+1])
        idx +=2
        a = x + y
        b = x - y
        points.append((a, b, i))
    
    sorted_a = sorted(points, key=lambda p: p[0])
    sorted_b = sorted(points, key=lambda p: p[1])
    
    pos_in_a = [0] * N
    for j in range(len(sorted_a)):
        pos_in_a[sorted_a[j][2]] = j
    
    pos_in_b = [0] * N
    for j in range(len(sorted_b)):
        pos_in_b[sorted_b[j][2]] = j
    
    max_a = max(p[0] for p in points)
    min_a = min(p[0] for p in points)
    max_b = max(p[1] for p in points)
    min_b = min(p[1] for p in points)
    
    min_p = float('inf')
    
    for point in points:
        a_i, b_i, idx = point
        # Compute max distance
        max_d = max(
            max_a - a_i,
            a_i - min_a,
            max_b - b_i,
            b_i - min_b
        )
        
        # Compute min distance
        min_d = float('inf')
        
        # Check in sorted_a
        pos = pos_in_a[idx]
        start = max(0, pos - 5)
        end = min(len(sorted_a) - 1, pos + 5)
        for j in range(start, end + 1):
            other = sorted_a[j]
            if other[2] == idx:
                continue
            current_d = max(abs(a_i - other[0]), abs(b_i - other[1]))
            if current_d < min_d:
                min_d = current_d
        
        # Check in sorted_b
        pos = pos_in_b[idx]
        start = max(0, pos - 5)
        end = min(len(sorted_b) - 1, pos + 5)
        for j in range(start, end + 1):
            other = sorted_b[j]
            if other[2] == idx:
                continue
            current_d = max(abs(a_i - other[0]), abs(b_i - other[1]))
            if current_d < min_d:
                min_d = current_d
        
        # Update min_p
        p_i = max_d - min_d
        if p_i < min_p:
            min_p = p_i
    
    print(min_p)

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