結果

問題 No.2436 Min Diff Distance
ユーザー gew1fw
提出日時 2025-06-12 18:40:38
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 3,128 bytes
コンパイル時間 293 ms
コンパイル使用メモリ 82,316 KB
実行使用メモリ 186,944 KB
最終ジャッジ日時 2025-06-12 18:40:45
合計ジャッジ時間 4,321 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 3 TLE * 1 -- * 19
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys

def main():
    input = sys.stdin.read().split()
    idx = 0
    N = int(input[idx])
    idx += 1
    X = []
    Y = []
    for _ in range(N):
        x = int(input[idx])
        y = int(input[idx + 1])
        X.append(x)
        Y.append(y)
        idx += 2
    
    u = [x + y for x, y in zip(X, Y)]
    v = [x - y for x, y in zip(X, Y)]
    
    max_u = max(u)
    min_u = min(u)
    max_v = max(v)
    min_v = min(v)
    
    # Generate sorted indices for each criteria
    sorted_x = sorted(range(N), key=lambda i: (X[i], Y[i]))
    sorted_y = sorted(range(N), key=lambda i: (Y[i], X[i]))
    sorted_u = sorted(range(N), key=lambda i: (u[i], X[i]))
    sorted_v = sorted(range(N), key=lambda i: (v[i], X[i]))
    
    # Precompute positions for each point in each sorted array
    pos_x = [0] * N
    for idx_sort, i in enumerate(sorted_x):
        pos_x[i] = idx_sort
    pos_y = [0] * N
    for idx_sort, i in enumerate(sorted_y):
        pos_y[i] = idx_sort
    pos_u = [0] * N
    for idx_sort, i in enumerate(sorted_u):
        pos_u[i] = idx_sort
    pos_v = [0] * N
    for idx_sort, i in enumerate(sorted_v):
        pos_v[i] = idx_sort
    
    k = 5
    min_p = float('inf')
    
    for i in range(N):
        current_u = u[i]
        current_v = v[i]
        
        # Calculate max_dist
        max_dist_u = max(current_u - min_u, max_u - current_u)
        max_dist_v = max(current_v - min_v, max_v - current_v)
        max_dist = max(max_dist_u, max_dist_v)
        
        # Calculate min_dist by checking neighbors in all four sorted arrays
        min_dist = float('inf')
        
        # Check sorted_x
        pos = pos_x[i]
        start = max(0, pos - k)
        end = min(len(sorted_x) - 1, pos + k)
        for j in sorted_x[start:end + 1]:
            if j == i:
                continue
            d = abs(X[i] - X[j]) + abs(Y[i] - Y[j])
            if d < min_dist:
                min_dist = d
        
        # Check sorted_y
        pos = pos_y[i]
        start = max(0, pos - k)
        end = min(len(sorted_y) - 1, pos + k)
        for j in sorted_y[start:end + 1]:
            if j == i:
                continue
            d = abs(X[i] - X[j]) + abs(Y[i] - Y[j])
            if d < min_dist:
                min_dist = d
        
        # Check sorted_u
        pos = pos_u[i]
        start = max(0, pos - k)
        end = min(len(sorted_u) - 1, pos + k)
        for j in sorted_u[start:end + 1]:
            if j == i:
                continue
            d = abs(X[i] - X[j]) + abs(Y[i] - Y[j])
            if d < min_dist:
                min_dist = d
        
        # Check sorted_v
        pos = pos_v[i]
        start = max(0, pos - k)
        end = min(len(sorted_v) - 1, pos + k)
        for j in sorted_v[start:end + 1]:
            if j == i:
                continue
            d = abs(X[i] - X[j]) + abs(Y[i] - Y[j])
            if d < min_dist:
                min_dist = d
        
        # 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