結果

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

ソースコード

diff # 

import sys

def main():
    n = int(sys.stdin.readline())
    points = []
    for _ in range(n):
        x, y = map(int, sys.stdin.readline().split())
        points.append((x, y))
    
    # Preprocess sorted indices for different criteria
    sorted_x = sorted(range(n), key=lambda i: (points[i][0], points[i][1]))
    sorted_y = sorted(range(n), key=lambda i: (points[i][1], points[i][0]))
    sorted_u = sorted(range(n), key=lambda i: (points[i][0] + points[i][1], points[i][0] - points[i][1]))
    sorted_v = sorted(range(n), key=lambda i: (points[i][0] - points[i][1], points[i][0] + points[i][1]))
    
    # Precompute positions for each point in each sorted list
    pos_x = [0] * n
    for idx, i in enumerate(sorted_x):
        pos_x[i] = idx
    pos_y = [0] * n
    for idx, i in enumerate(sorted_y):
        pos_y[i] = idx
    pos_u = [0] * n
    for idx, i in enumerate(sorted_u):
        pos_u[i] = idx
    pos_v = [0] * n
    for idx, i in enumerate(sorted_v):
        pos_v[i] = idx
    
    # Compute u and v for all points
    u = [x + y for x, y in points]
    v = [x - y for x, y in points]
    max_u, min_u = max(u), min(u)
    max_v, min_v = max(v), min(v)
    
    min_p = float('inf')
    k = 5  # Number of neighbors to check on each side
    
    for i in range(n):
        x_i, y_i = points[i]
        current_u = u[i]
        current_v = v[i]
        # Calculate maximum Manhattan distance
        max_dist = max(
            current_u - min_u,
            max_u - current_u,
            current_v - min_v,
            max_v - current_v
        )
        # Initialize minimum distance to a large value
        min_dist = float('inf')
        
        # Check neighbors in sorted_x
        idx = pos_x[i]
        start = max(0, idx - k)
        end = min(len(sorted_x) - 1, idx + k)
        for j in sorted_x[start:end+1]:
            if j == i:
                continue
            dx = abs(x_i - points[j][0])
            dy = abs(y_i - points[j][1])
            min_dist = min(min_dist, dx + dy)
        
        # Check neighbors in sorted_y
        idx = pos_y[i]
        start = max(0, idx - k)
        end = min(len(sorted_y) - 1, idx + k)
        for j in sorted_y[start:end+1]:
            if j == i:
                continue
            dx = abs(x_i - points[j][0])
            dy = abs(y_i - points[j][1])
            min_dist = min(min_dist, dx + dy)
        
        # Check neighbors in sorted_u
        idx = pos_u[i]
        start = max(0, idx - k)
        end = min(len(sorted_u) - 1, idx + k)
        for j in sorted_u[start:end+1]:
            if j == i:
                continue
            dx = abs(x_i - points[j][0])
            dy = abs(y_i - points[j][1])
            min_dist = min(min_dist, dx + dy)
        
        # Check neighbors in sorted_v
        idx = pos_v[i]
        start = max(0, idx - k)
        end = min(len(sorted_v) - 1, idx + k)
        for j in sorted_v[start:end+1]:
            if j == i:
                continue
            dx = abs(x_i - points[j][0])
            dy = abs(y_i - points[j][1])
            min_dist = min(min_dist, dx + dy)
        
        # Calculate P_i and update min_p
        p_i = abs(max_dist - min_dist)
        if p_i < min_p:
            min_p = p_i
    
    print(min_p)

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