結果

問題 No.1998 Manhattan Restaurant
ユーザー lam6er
提出日時 2025-03-20 20:39:21
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 3,431 bytes
コンパイル時間 142 ms
コンパイル使用メモリ 82,768 KB
実行使用メモリ 242,620 KB
最終ジャッジ日時 2025-03-20 20:39:34
合計ジャッジ時間 5,405 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 8 WA * 3 TLE * 1 -- * 19
権限があれば一括ダウンロードができます

ソースコード

diff # 

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    idx = 0
    N = int(data[idx])
    idx +=1
    points = []
    for _ in range(N):
        x = int(data[idx])
        y = int(data[idx+1])
        idx +=2
        u = x + y
        v = x - y
        points.append((u, v))
    
    if N <= 1:
        print(0)
        return
    
    min_u = max_u = points[0][0]
    min_v = max_v = points[0][1]
    for u, v in points:
        min_u = min(min_u, u)
        max_u = max(max_u, u)
        min_v = min(min_v, v)
        max_v = max(max_v, v)
    
    # Required D for one square
    initial_D = max( (max_u - min_u) // 2, (max_v - min_v) // 2 )
    low = 0
    high = initial_D
    
    def is_possible(D):
        orders = [
            (lambda p: p[0], False),    # sorted by u ascending
            (lambda p: -p[0], False),   # sorted by u descending
            (lambda p: p[1], False),    # sorted by v ascending
            (lambda p: -p[1], False)    # sorted by v descending
        ]
        for key_func, _ in orders:
            sorted_points = sorted(points, key=key_func)
            n = len(sorted_points)
            # Precompute prefix min and max
            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(1, n+1):
                u, v = sorted_points[i-1]
                prefix_min_u[i] = min(prefix_min_u[i-1], u)
                prefix_max_u[i] = max(prefix_max_u[i-1], u)
                prefix_min_v[i] = min(prefix_min_v[i-1], v)
                prefix_max_v[i] = max(prefix_max_v[i-1], v)
            
            # Precompute suffix min and max
            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):
                u, v = sorted_points[i]
                suffix_min_u[i] = min(suffix_min_u[i+1], u)
                suffix_max_u[i] = max(suffix_max_u[i+1], u)
                suffix_min_v[i] = min(suffix_min_v[i+1], v)
                suffix_max_v[i] = max(suffix_max_v[i+1], v)
            
            # Check all possible splits
            for i in range(n+1):
                # Compute left group D
                if i ==0:
                    left_du =0
                    left_dv =0
                else:
                    left_du = (prefix_max_u[i] - prefix_min_u[i]) //2
                    left_dv = (prefix_max_v[i] - prefix_min_v[i]) //2
                left_max = max(left_du, left_dv)
                # Compute right group D
                if i ==n:
                    right_du =0
                    right_dv =0
                else:
                    right_du = (suffix_max_u[i] - suffix_min_u[i]) //2
                    right_dv = (suffix_max_v[i] - suffix_min_v[i]) //2
                right_max = max(right_du, right_dv)
                if left_max <= D and right_max <= D:
                    return True
        return False
    
    answer = high
    while low <= high:
        mid = (low + high) //2
        if is_possible(mid):
            answer = mid
            high = mid -1
        else:
            low = mid +1
    print(answer)

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