結果

問題 No.2436 Min Diff Distance
ユーザー lam6er
提出日時 2025-04-15 21:43:44
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,981 bytes
コンパイル時間 223 ms
コンパイル使用メモリ 82,376 KB
実行使用メモリ 239,732 KB
最終ジャッジ日時 2025-04-15 21:45:22
合計ジャッジ時間 4,257 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
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 = [(data[2*i], data[2*i+1]) for i in range(n)]
    
    # Preprocess candidates for max distance
    # Sort for x+y and x-y to get extreme points
    x_plus_y = sorted(points, key=lambda p: (p[0] + p[1]), reverse=True)
    x_minus_y = sorted(points, key=lambda p: (p[0] - p[1]), reverse=True)
    
    max_x_plus_y = x_plus_y[:2]
    min_x_plus_y = x_plus_y[-2:] if len(x_plus_y) >= 2 else []
    max_x_minus_y = x_minus_y[:2]
    min_x_minus_y = x_minus_y[-2:] if len(x_minus_y) >= 2 else []
    
    candidates = []
    candidates.extend(max_x_plus_y)
    candidates.extend(min_x_plus_y)
    candidates.extend(max_x_minus_y)
    candidates.extend(min_x_minus_y)
    # Remove duplicates while preserving order
    seen = set()
    unique_candidates = []
    for p in candidates:
        if p not in seen:
            seen.add(p)
            unique_candidates.append(p)
    candidates = unique_candidates
    
    # Sort points for min distance checking
    sorted_x = sorted(points, key=lambda p: (p[0], p[1]))
    sorted_y = sorted(points, key=lambda p: (p[1], p[0]))
    
    # Build index maps
    index_x = {(x, y): i for i, (x, y) in enumerate(sorted_x)}
    index_y = {(x, y): i for i, (x, y) in enumerate(sorted_y)}
    
    k = 5  # Adjust this value based on testing
    min_p = float('inf')
    
    for (x, y) in points:
        # Compute max distance
        max_dist = 0
        for p in candidates:
            if p == (x, y):
                continue
            d = abs(x - p[0]) + abs(y - p[1])
            if d > max_dist:
                max_dist = d
        
        # Compute min distance
        min_dist = float('inf')
        # Check in sorted_x
        if (x, y) in index_x:
            idx_x = index_x[(x, y)]
            start_x = max(0, idx_x - k)
            end_x = min(len(sorted_x) - 1, idx_x + k)
            for j in range(start_x, end_x + 1):
                ox, oy = sorted_x[j]
                if ox == x and oy == y:
                    continue
                d = abs(x - ox) + abs(y - oy)
                if d < min_dist:
                    min_dist = d
        
        # Check in sorted_y
        if (x, y) in index_y:
            idx_y = index_y[(x, y)]
            start_y = max(0, idx_y - k)
            end_y = min(len(sorted_y) - 1, idx_y + k)
            for j in range(start_y, end_y + 1):
                ox, oy = sorted_y[j]
                if ox == x and oy == y:
                    continue
                d = abs(x - ox) + abs(y - oy)
                if d < min_dist:
                    min_dist = d
        
        # Compute P_i
        p_i = abs(max_dist - (min_dist if min_dist != float('inf') else 0))
        if p_i < min_p:
            min_p = p_i
            if min_p == 0:
                print(0)
                return
    
    print(min_p)

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