結果

問題 No.2436 Min Diff Distance
ユーザー lam6er
提出日時 2025-03-31 17:26:15
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,411 bytes
コンパイル時間 219 ms
コンパイル使用メモリ 82,408 KB
実行使用メモリ 187,160 KB
最終ジャッジ日時 2025-03-31 17:27:36
合計ジャッジ時間 5,407 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 3 TLE * 1 -- * 19
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys

def main():
    input = sys.stdin.read().split()
    n = int(input[0])
    data = list(map(int, input[1:]))
    points = []
    for i in range(n):
        x = data[2*i]
        y = data[2*i + 1]
        points.append((x, y))
    
    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)
    
    # Prepare u_sorted and v_sorted lists with indexes
    u_sorted = sorted([(u[i], x, y, i) for i, (x, y) in enumerate(points)], key=lambda x: x[0])
    v_sorted = sorted([(v[i], x, y, i) for i, (x, y) in enumerate(points)], key=lambda x: x[0])
    
    # Prepare u_pos and v_pos to store the positions of each point in sorted lists
    u_pos = [0] * n
    for idx, (_, _, _, i) in enumerate(u_sorted):
        u_pos[i] = idx
    
    v_pos = [0] * n
    for idx, (_, _, _, i) in enumerate(v_sorted):
        v_pos[i] = idx
    
    min_p = float('inf')
    k = 5  # Number of nearby points to check in each direction
    
    for i in range(n):
        # Collect candidate indices for min distance checks
        candidates = set()
        xi, yi = points[i]
        
        # Check nearby points in u_sorted
        j_u = u_pos[i]
        start_u = max(0, j_u - k)
        end_u = min(len(u_sorted) - 1, j_u + k)
        for pos in range(start_u, end_u + 1):
            _, xj, yj, idx = u_sorted[pos]
            if idx != i:
                candidates.add(idx)
        
        # Check nearby points in v_sorted
        j_v = v_pos[i]
        start_v = max(0, j_v - k)
        end_v = min(len(v_sorted) - 1, j_v + k)
        for pos in range(start_v, end_v + 1):
            _, xj, yj, idx = v_sorted[pos]
            if idx != i:
                candidates.add(idx)
        
        # Calculate minimal distance
        min_dist = float('inf')
        for j in candidates:
            xj, yj = points[j]
            distance = abs(xi - xj) + abs(yi - yj)
            if distance < min_dist:
                min_dist = distance
        
        # Compute max_dist
        current_u = u[i]
        current_v = v[i]
        a = current_u - min_u
        b = max_u - current_u
        c = current_v - min_v
        d = max_v - current_v
        max_dist = max(a, b, c, d)
        
        p = max_dist - min_dist
        if p < min_p:
            min_p = p
    
    print(min_p)

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