結果

問題 No.1998 Manhattan Restaurant
ユーザー gew1fw
提出日時 2025-06-12 21:11:04
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 4,542 bytes
コンパイル時間 244 ms
コンパイル使用メモリ 81,792 KB
実行使用メモリ 260,732 KB
最終ジャッジ日時 2025-06-12 21:12:46
合計ジャッジ時間 19,318 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
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
    
    sorted_by_u = sorted(points, key=lambda x: x[0])
    sorted_by_v = sorted(points, key=lambda x: x[1])
    
    min_u = min(p[0] for p in points)
    max_u = max(p[0] for p in points)
    min_v = min(p[1] for p in points)
    max_v = max(p[1] for p in points)
    
    low = 0
    high = max(max_u - min_u, max_v - min_v)
    answer = high
    
    while low <= high:
        mid = (low + high) // 2
        
        # Check if entire set can be covered by one square
        if (max_u - min_u) <= 2 * mid and (max_v - min_v) <= 2 * mid:
            answer = mid
            high = mid - 1
            continue
        
        # Check split along u
        n = len(sorted_by_u)
        prefix_min_u = [float('inf')] * (n + 1)
        prefix_max_u = [-float('inf')] * (n + 1)
        prefix_min_v = [float('inf')] * (n + 1)
        prefix_max_v = [-float('inf')] * (n + 1)
        
        for i in range(n):
            current_u, current_v = sorted_by_u[i]
            prefix_min_u[i+1] = min(prefix_min_u[i], current_u)
            prefix_max_u[i+1] = max(prefix_max_u[i], current_u)
            prefix_min_v[i+1] = min(prefix_min_v[i], current_v)
            prefix_max_v[i+1] = max(prefix_max_v[i], current_v)
        
        suffix_min_u = [float('inf')] * (n + 1)
        suffix_max_u = [-float('inf')] * (n + 1)
        suffix_min_v = [float('inf')] * (n + 1)
        suffix_max_v = [-float('inf')] * (n + 1)
        
        for i in range(n-1, -1, -1):
            current_u, current_v = sorted_by_u[i]
            suffix_min_u[i] = min(suffix_min_u[i+1], current_u)
            suffix_max_u[i] = max(suffix_max_u[i+1], current_u)
            suffix_min_v[i] = min(suffix_min_v[i+1], current_v)
            suffix_max_v[i] = max(suffix_max_v[i+1], current_v)
        
        found = False
        for i in range(n+1):
            left_u_span = prefix_max_u[i] - prefix_min_u[i]
            left_v_span = prefix_max_v[i] - prefix_min_v[i]
            right_u_span = suffix_max_u[i] - suffix_min_u[i]
            right_v_span = suffix_max_v[i] - suffix_min_v[i]
            if left_u_span <= 2 * mid and left_v_span <= 2 * mid and right_u_span <= 2 * mid and right_v_span <= 2 * mid:
                found = True
                break
        if found:
            answer = mid
            high = mid - 1
            continue
        
        # Check split along v
        n = len(sorted_by_v)
        prefix_min_u_v = [float('inf')] * (n + 1)
        prefix_max_u_v = [-float('inf')] * (n + 1)
        prefix_min_v_v = [float('inf')] * (n + 1)
        prefix_max_v_v = [-float('inf')] * (n + 1)
        
        for i in range(n):
            current_u, current_v = sorted_by_v[i]
            prefix_min_u_v[i+1] = min(prefix_min_u_v[i], current_u)
            prefix_max_u_v[i+1] = max(prefix_max_u_v[i], current_u)
            prefix_min_v_v[i+1] = min(prefix_min_v_v[i], current_v)
            prefix_max_v_v[i+1] = max(prefix_max_v_v[i], current_v)
        
        suffix_min_u_v = [float('inf')] * (n + 1)
        suffix_max_u_v = [-float('inf')] * (n + 1)
        suffix_min_v_v = [float('inf')] * (n + 1)
        suffix_max_v_v = [-float('inf')] * (n + 1)
        
        for i in range(n-1, -1, -1):
            current_u, current_v = sorted_by_v[i]
            suffix_min_u_v[i] = min(suffix_min_u_v[i+1], current_u)
            suffix_max_u_v[i] = max(suffix_max_u_v[i+1], current_u)
            suffix_min_v_v[i] = min(suffix_min_v_v[i+1], current_v)
            suffix_max_v_v[i] = max(suffix_max_v_v[i+1], current_v)
        
        for i in range(n+1):
            left_u_span = prefix_max_u_v[i] - prefix_min_u_v[i]
            left_v_span = prefix_max_v_v[i] - prefix_min_v_v[i]
            right_u_span = suffix_max_u_v[i] - suffix_min_u_v[i]
            right_v_span = suffix_max_v_v[i] - suffix_min_v_v[i]
            if left_u_span <= 2 * mid and left_v_span <= 2 * mid and right_u_span <= 2 * mid and right_v_span <= 2 * mid:
                found = True
                break
        
        if found:
            answer = mid
            high = mid - 1
        else:
            low = mid + 1
    
    print(answer)

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