結果

問題 No.2436 Min Diff Distance
ユーザー lam6er
提出日時 2025-04-15 21:45:09
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 3,438 bytes
コンパイル時間 414 ms
コンパイル使用メモリ 82,148 KB
実行使用メモリ 274,488 KB
最終ジャッジ日時 2025-04-15 21:46:08
合計ジャッジ時間 4,031 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 3 TLE * 1 -- * 19
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys

def main():
    input = sys.stdin.read().split()
    idx = 0
    n = int(input[idx])
    idx += 1
    points = []
    for _ in range(n):
        x = int(input[idx])
        y = int(input[idx+1])
        points.append((x, y))
        idx += 2
    
    # Precompute sums and diffs for max distance calculation
    sums = [x + y for x, y in points]
    diffs = [x - y for x, y in points]
    max_sum = max(sums)
    min_sum = min(sums)
    max_diff = max(diffs)
    min_diff = min(diffs)
    
    # Prepare sorted arrays and their position dictionaries
    sorted_x = sorted(points, key=lambda p: (p[0], p[1]))
    sorted_y = sorted(points, key=lambda p: (p[1], p[0]))
    sorted_sum = sorted(points, key=lambda p: (p[0] + p[1], p[0], p[1]))
    sorted_diff = sorted(points, key=lambda p: (p[0] - p[1], p[0], p[1]))
    
    # Create dictionaries to find the index of each point in the sorted arrays
    pos_in_x = {point: idx for idx, point in enumerate(sorted_x)}
    pos_in_y = {point: idx for idx, point in enumerate(sorted_y)}
    pos_in_sum = {point: idx for idx, point in enumerate(sorted_sum)}
    pos_in_diff = {point: idx for idx, point in enumerate(sorted_diff)}
    
    min_p = float('inf')
    m = 5  # Number of neighbors to check on each side
    
    for point in points:
        x, y = point
        
        # Compute max_dist
        current_sum = x + y
        current_diff = x - y
        max_dist = max(
            current_sum - min_sum,
            max_sum - current_sum,
            current_diff - min_diff,
            max_diff - current_diff
        )
        
        # Compute min_dist by checking neighbors in all four sorted arrays
        min_dist = float('inf')
        
        # Check in sorted_x
        k = pos_in_x[point]
        start = max(0, k - m)
        end = min(len(sorted_x) - 1, k + m)
        for i in range(start, end + 1):
            other = sorted_x[i]
            if other == point:
                continue
            d = abs(x - other[0]) + abs(y - other[1])
            if d < min_dist:
                min_dist = d
        
        # Check in sorted_y
        k = pos_in_y[point]
        start = max(0, k - m)
        end = min(len(sorted_y) - 1, k + m)
        for i in range(start, end + 1):
            other = sorted_y[i]
            if other == point:
                continue
            d = abs(x - other[0]) + abs(y - other[1])
            if d < min_dist:
                min_dist = d
        
        # Check in sorted_sum
        k = pos_in_sum[point]
        start = max(0, k - m)
        end = min(len(sorted_sum) - 1, k + m)
        for i in range(start, end + 1):
            other = sorted_sum[i]
            if other == point:
                continue
            d = abs(x - other[0]) + abs(y - other[1])
            if d < min_dist:
                min_dist = d
        
        # Check in sorted_diff
        k = pos_in_diff[point]
        start = max(0, k - m)
        end = min(len(sorted_diff) - 1, k + m)
        for i in range(start, end + 1):
            other = sorted_diff[i]
            if other == point:
                continue
            d = abs(x - other[0]) + abs(y - other[1])
            if d < min_dist:
                min_dist = d
        
        # 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