結果

問題 No.1998 Manhattan Restaurant
ユーザー lam6er
提出日時 2025-04-16 00:00:20
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,458 bytes
コンパイル時間 203 ms
コンパイル使用メモリ 82,472 KB
実行使用メモリ 120,312 KB
最終ジャッジ日時 2025-04-16 00:02:30
合計ジャッジ時間 8,057 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 10 WA * 21
権限があれば一括ダウンロードができます

ソースコード

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])
        idx += 2
        u = x + y
        v = x - y
        points.append((u, v))
    
    if N == 0:
        print(0)
        return
    
    def compute_min_candidate(sorted_points):
        n = len(sorted_points)
        prefix_max_u = [-float('inf')] * (n + 1)
        prefix_min_u = [float('inf')] * (n + 1)
        prefix_max_v = [-float('inf')] * (n + 1)
        prefix_min_v = [float('inf')] * (n + 1)
        
        for i in range(1, n + 1):
            u, v = sorted_points[i-1]
            prefix_max_u[i] = max(prefix_max_u[i-1], u)
            prefix_min_u[i] = min(prefix_min_u[i-1], u)
            prefix_max_v[i] = max(prefix_max_v[i-1], v)
            prefix_min_v[i] = min(prefix_min_v[i-1], v)
        
        suffix_max_u = [-float('inf')] * (n + 1)
        suffix_min_u = [float('inf')] * (n + 1)
        suffix_max_v = [-float('inf')] * (n + 1)
        suffix_min_v = [float('inf')] * (n + 1)
        
        for i in range(n-1, -1, -1):
            u, v = sorted_points[i]
            suffix_max_u[i] = max(suffix_max_u[i+1], u)
            suffix_min_u[i] = min(suffix_min_u[i+1], u)
            suffix_max_v[i] = max(suffix_max_v[i+1], v)
            suffix_min_v[i] = min(suffix_min_v[i+1], v)
        
        min_candidate = float('inf')
        for i in range(n + 1):
            left_du = prefix_max_u[i] - prefix_min_u[i] if i != 0 else 0
            left_dv = prefix_max_v[i] - prefix_min_v[i] if i != 0 else 0
            left_dim = max(left_du, left_dv)
            
            right_du = suffix_max_u[i] - suffix_min_u[i] if i != n else 0
            right_dv = suffix_max_v[i] - suffix_min_v[i] if i != n else 0
            right_dim = max(right_du, right_dv)
            
            current_candidate = max(left_dim, right_dim)
            if current_candidate < min_candidate:
                min_candidate = current_candidate
        
        return min_candidate
    
    sorted_u = sorted(points, key=lambda x: x[0])
    candidate_u = compute_min_candidate(sorted_u)
    
    sorted_v = sorted(points, key=lambda x: x[1])
    candidate_v = compute_min_candidate(sorted_v)
    
    minimal_candidate = min(candidate_u, candidate_v)
    print(minimal_candidate // 2)

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