結果

問題 No.2436 Min Diff Distance
ユーザー gew1fw
提出日時 2025-06-12 16:23:38
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,017 bytes
コンパイル時間 173 ms
コンパイル使用メモリ 82,304 KB
実行使用メモリ 132,848 KB
最終ジャッジ日時 2025-06-12 16:24:30
合計ジャッジ時間 32,961 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 7 WA * 7 TLE * 9
権限があれば一括ダウンロードができます

ソースコード

diff # 

import bisect

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    
    N = int(data[0])
    points = []
    idx = 1
    for _ in range(N):
        x = int(data[idx])
        y = int(data[idx+1])
        points.append((x, y))
        idx += 2
    
    a = [x + y for x, y in points]
    b = [x - y for x, y in points]
    
    sorted_a = sorted((a[i], i) for i in range(N))
    sorted_b = sorted((b[i], i) for i in range(N))
    
    a_max = max(a)
    a_min = min(a)
    b_max = max(b)
    b_min = min(b)
    
    extremal_j = [sorted_a[0][1], sorted_a[-1][1], sorted_b[0][1], sorted_b[-1][1]]
    extremal_j = list(set(extremal_j))
    
    min_p = float('inf')
    
    for i in range(N):
        current_a = a[i]
        current_b = b[i]
        
        max_distance = max(
            a_max - current_a,
            current_a - a_min,
            b_max - current_b,
            current_b - b_min
        )
        
        candidates = set(extremal_j)
        
        # Add nearby a points
        pos = bisect.bisect_left(sorted_a, (current_a, -1))
        start = max(0, pos - 5)
        end = min(pos + 5, N)
        for j in range(start, end):
            candidates.add(sorted_a[j][1])
        
        # Add nearby b points
        pos = bisect.bisect_left(sorted_b, (current_b, -1))
        start = max(0, pos - 5)
        end = min(pos + 5, N)
        for j in range(start, end):
            candidates.add(sorted_b[j][1])
        
        min_distance = float('inf')
        for j in candidates:
            if j == i:
                continue
            diff_a = abs(current_a - a[j])
            diff_b = abs(current_b - b[j])
            manhattan = max(diff_a, diff_b)
            if manhattan < min_distance:
                min_distance = manhattan
        
        if min_distance != float('inf'):
            P_i = max_distance - min_distance
            if P_i < min_p:
                min_p = P_i
    
    print(min_p)

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