結果

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

ソースコード

diff # 

import sys

def main():
    n = int(sys.stdin.readline())
    points = [tuple(map(int, sys.stdin.readline().split())) for _ in range(n)]
    u = [x + y for x, y in points]
    v = [x - y for x, y in points]
    
    # Preprocess sorted_u and u_indices
    sorted_u = sorted((u[j], j) for j in range(n))
    u_indices = [0] * n
    for idx, (val, j) in enumerate(sorted_u):
        u_indices[j] = idx
    
    # Preprocess sorted_v and v_indices
    sorted_v = sorted((v[j], j) for j in range(n))
    v_indices = [0] * n
    for idx, (val, j) in enumerate(sorted_v):
        v_indices[j] = idx
    
    max_u = max(u)
    min_u = min(u)
    max_v = max(v)
    min_v = min(v)
    
    k = 5  # 可以根据情况调整k的值
    min_p = float('inf')
    
    for i in range(n):
        # Calculate max_d
        max_d = max(u[i] - min_u, max_u - u[i], v[i] - min_v, max_v - v[i])
        
        # Calculate min_d by checking nearby points in sorted_u and sorted_v
        min_d = float('inf')
        
        # Check in sorted_u
        pos_u = u_indices[i]
        start = max(0, pos_u - k)
        end = min(n, pos_u + k + 1)
        for j_pos in range(start, end):
            j = sorted_u[j_pos][1]
            if j != i:
                d = max(abs(u[i] - u[j]), abs(v[i] - v[j]))
                if d < min_d:
                    min_d = d
        
        # Check in sorted_v
        pos_v = v_indices[i]
        start = max(0, pos_v - k)
        end = min(n, pos_v + k + 1)
        for j_pos in range(start, end):
            j = sorted_v[j_pos][1]
            if j != i:
                d = max(abs(u[i] - u[j]), abs(v[i] - v[j]))
                if d < min_d:
                    min_d = d
        
        # Calculate P_i
        P_i = abs(max_d - min_d)
        if P_i < min_p:
            min_p = P_i
    
    print(min_p)

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