結果

問題 No.2436 Min Diff Distance
ユーザー lam6er
提出日時 2025-03-31 17:50:34
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,207 bytes
コンパイル時間 220 ms
コンパイル使用メモリ 82,080 KB
実行使用メモリ 54,488 KB
最終ジャッジ日時 2025-03-31 17:51:23
合計ジャッジ時間 4,796 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 3 TLE * 1 -- * 19
権限があれば一括ダウンロードができます

ソースコード

diff # 

import bisect

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    n = int(data[0])
    points = []
    idx = 1
    for i in range(n):
        x = int(data[idx])
        y = int(data[idx+1])
        points.append((x, y))
        idx += 2
    
    # Precompute a and b for each point
    sorted_a = []
    sorted_b = []
    for x, y in points:
        a = x + y
        b = x - y
        sorted_a.append((a, x, y))
        sorted_b.append((b, x, y))
    
    # Sort the lists
    sorted_a.sort()
    sorted_b.sort()
    
    # Precompute global min and max for a and b
    min_a = sorted_a[0][0]
    max_a = sorted_a[-1][0]
    min_b = sorted_b[0][0]
    max_b = sorted_b[-1][0]
    
    min_p = float('inf')
    
    for x, y in points:
        a = x + y
        b_val = x - y
        
        # Compute max_dist
        max_dist = max(
            a - min_a,
            max_a - a,
            b_val - min_b,
            max_b - b_val
        )
        
        # Compute min_dist by checking neighbors in sorted_a and sorted_b
        min_dist = float('inf')
        
        # Check in sorted_a
        key_a = (a, x, y)
        idx_a = bisect.bisect_left(sorted_a, key_a)
        # Check up to 5 neighbors before and after
        start_a = max(0, idx_a - 5)
        end_a = min(len(sorted_a), idx_a + 6)
        for j in range(start_a, end_a):
            if j == idx_a:
                continue
            a_j, x_j, y_j = sorted_a[j]
            dist = abs(x - x_j) + abs(y - y_j)
            if dist < min_dist:
                min_dist = dist
        
        # Check in sorted_b
        key_b = (b_val, x, y)
        idx_b = bisect.bisect_left(sorted_b, key_b)
        start_b = max(0, idx_b - 5)
        end_b = min(len(sorted_b), idx_b + 6)
        for j in range(start_b, end_b):
            if j == idx_b:
                continue
            b_j, x_j, y_j = sorted_b[j]
            dist = abs(x - x_j) + abs(y - y_j)
            if dist < min_dist:
                min_dist = dist
        
        # Compute P_i
        p_i = abs(max_dist - min_dist)
        if p_i < min_p:
            min_p = p_i
    
    print(min_p)

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