結果

問題 No.2436 Min Diff Distance
ユーザー gew1fw
提出日時 2025-06-12 14:17:00
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 4,040 bytes
コンパイル時間 354 ms
コンパイル使用メモリ 82,356 KB
実行使用メモリ 157,196 KB
最終ジャッジ日時 2025-06-12 14:17:39
合計ジャッジ時間 4,311 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 7 WA * 6 TLE * 10
権限があれば一括ダウンロードができます

ソースコード

diff # 

import bisect

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    N = int(data[0])
    points = []
    idx = 1
    u = []
    v = []
    for i in range(N):
        x = int(data[idx])
        y = int(data[idx+1])
        idx += 2
        points.append((x, y))
        u_val = x + y
        v_val = x - y
        u.append(u_val)
        v.append(v_val)
    
    # Precompute sorted_u and sorted_v
    sorted_u = sorted([(u[i], i) for i in range(N)], key=lambda x: (x[0], x[1]))
    sorted_v = sorted([(v[i], i) for i in range(N)], key=lambda x: (x[0], x[1]))
    
    # Function to compute max and min info
    def get_max_min_info(arr):
        sorted_desc = sorted(arr, reverse=True)
        max1 = sorted_desc[0]
        count_max1 = 1
        i = 1
        while i < len(sorted_desc) and sorted_desc[i] == max1:
            count_max1 += 1
            i += 1
        max2 = sorted_desc[i] if i < len(sorted_desc) else -float('inf')
        
        sorted_asc = sorted(arr)
        min1 = sorted_asc[0]
        count_min1 = 1
        i = 1
        while i < len(sorted_asc) and sorted_asc[i] == min1:
            count_min1 += 1
            i += 1
        min2 = sorted_asc[i] if i < len(sorted_asc) else float('inf')
        return (max1, count_max1, max2), (min1, count_min1, min2)
    
    (max_u_info, min_u_info) = get_max_min_info(u)
    (max_v_info, min_v_info) = get_max_min_info(v)
    
    max1_u, count_max1_u, max2_u = max_u_info
    min1_u, count_min1_u, min2_u = min_u_info
    max1_v, count_max1_v, max2_v = max_v_info
    min1_v, count_min1_v, min2_v = min_v_info
    
    K = 5
    min_P = float('inf')
    
    for i in range(N):
        current_u = u[i]
        current_v = v[i]
        
        # Compute max_chebyshev_i
        # For u
        if current_u == max1_u:
            if count_max1_u > 1:
                max_u_excl = max1_u
            else:
                max_u_excl = max2_u
        else:
            max_u_excl = max1_u
        
        if current_u == min1_u:
            if count_min1_u > 1:
                min_u_excl = min1_u
            else:
                min_u_excl = min2_u
        else:
            min_u_excl = min1_u
        
        a = max_u_excl - current_u
        b = current_u - min_u_excl
        
        # For v
        if current_v == max1_v:
            if count_max1_v > 1:
                max_v_excl = max1_v
            else:
                max_v_excl = max2_v
        else:
            max_v_excl = max1_v
        
        if current_v == min1_v:
            if count_min1_v > 1:
                min_v_excl = min1_v
            else:
                min_v_excl = min2_v
        else:
            min_v_excl = min1_v
        
        c = max_v_excl - current_v
        d = current_v - min_v_excl
        
        max_chebyshev = max(a, b, c, d)
        
        # Compute min_chebyshev
        min_dist = float('inf')
        
        # Check in sorted_u
        target = (current_u, i)
        pos = bisect.bisect_left(sorted_u, target)
        start = max(0, pos - K)
        end = min(len(sorted_u), pos + K + 1)
        for j in range(start, end):
            other_u, other_i = sorted_u[j]
            if other_i == i:
                continue
            dist = max(abs(current_u - other_u), abs(current_v - v[other_i]))
            if dist < min_dist:
                min_dist = dist
        
        # Check in sorted_v
        target_v = (current_v, i)
        pos_v = bisect.bisect_left(sorted_v, target_v)
        start_v = max(0, pos_v - K)
        end_v = min(len(sorted_v), pos_v + K + 1)
        for j in range(start_v, end_v):
            other_v, other_i = sorted_v[j]
            if other_i == i:
                continue
            dist = max(abs(current_u - u[other_i]), abs(current_v - other_v))
            if dist < min_dist:
                min_dist = dist
        
        P_i = max_chebyshev - min_dist
        if P_i < min_P:
            min_P = P_i
    
    print(min_P)

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