結果

問題 No.2436 Min Diff Distance
ユーザー gew1fw
提出日時 2025-06-12 13:22:53
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 3,205 bytes
コンパイル時間 188 ms
コンパイル使用メモリ 82,560 KB
実行使用メモリ 52,992 KB
最終ジャッジ日時 2025-06-12 13:26:19
合計ジャッジ時間 4,905 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
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))
    
    sum_values = [x + y for x, y in points]
    diff_values = [x - y for x, y in points]
    
    max_sum_val = max(sum_values)
    min_sum_val = min(sum_values)
    max_diff_val = max(diff_values)
    min_diff_val = min(diff_values)
    
    max_sum_point = points[sum_values.index(max_sum_val)]
    min_sum_point = points[sum_values.index(min_sum_val)]
    max_diff_point = points[diff_values.index(max_diff_val)]
    min_diff_point = points[diff_values.index(min_diff_val)]
    
    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]))
    
    index_x = {p: idx for idx, p in enumerate(sorted_x)}
    index_y = {p: idx for idx, p in enumerate(sorted_y)}
    index_sum = {p: idx for idx, p in enumerate(sorted_sum)}
    index_diff = {p: idx for idx, p in enumerate(sorted_diff)}
    
    k = 5
    min_p = float('inf')
    
    for p in points:
        x, y = p
        
        d_max_sum = abs(x - max_sum_point[0]) + abs(y - max_sum_point[1])
        d_min_sum = abs(x - min_sum_point[0]) + abs(y - min_sum_point[1])
        d_max_diff = abs(x - max_diff_point[0]) + abs(y - max_diff_point[1])
        d_min_diff = abs(x - min_diff_point[0]) + abs(y - min_diff_point[1])
        max_d = max(d_max_sum, d_min_sum, d_max_diff, d_min_diff)
        
        min_d = float('inf')
        
        idx = index_x[p]
        start = max(0, idx - k)
        end = min(len(sorted_x) - 1, idx + k)
        for j in range(start, end + 1):
            other = sorted_x[j]
            if other == p:
                continue
            d = abs(x - other[0]) + abs(y - other[1])
            if d < min_d:
                min_d = d
        
        idx = index_y[p]
        start = max(0, idx - k)
        end = min(len(sorted_y) - 1, idx + k)
        for j in range(start, end + 1):
            other = sorted_y[j]
            if other == p:
                continue
            d = abs(x - other[0]) + abs(y - other[1])
            if d < min_d:
                min_d = d
        
        idx = index_sum[p]
        start = max(0, idx - k)
        end = min(len(sorted_sum) - 1, idx + k)
        for j in range(start, end + 1):
            other = sorted_sum[j]
            if other == p:
                continue
            d = abs(x - other[0]) + abs(y - other[1])
            if d < min_d:
                min_d = d
        
        idx = index_diff[p]
        start = max(0, idx - k)
        end = min(len(sorted_diff) - 1, idx + k)
        for j in range(start, end + 1):
            other = sorted_diff[j]
            if other == p:
                continue
            d = abs(x - other[0]) + abs(y - other[1])
            if d < min_d:
                min_d = d
        
        p_i = abs(max_d - min_d)
        if p_i < min_p:
            min_p = p_i
    
    print(min_p)

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