結果

問題 No.1998 Manhattan Restaurant
ユーザー gew1fw
提出日時 2025-06-12 16:31:48
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 4,937 bytes
コンパイル時間 179 ms
コンパイル使用メモリ 82,272 KB
実行使用メモリ 195,764 KB
最終ジャッジ日時 2025-06-12 16:31:57
合計ジャッジ時間 5,283 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 8 WA * 3 TLE * 1 -- * 19
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys

class Point:
    def __init__(self, x, y):
        self.x = x
        self.y = y
        self.u = x + y
        self.v = x - y

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
        points.append(Point(x, y))
    
    if N <= 1:
        print(0)
        return
    
    U = [p.u for p in points]
    V = [p.v for p in points]
    U_min = min(U)
    U_max = max(U)
    V_min = min(V)
    V_max = max(V)
    D_single = max( (U_max - U_min) // 2, (V_max - V_min) // 2 )
    
    low = 0
    high = D_single
    
    def is_possible(D):
        if (U_max - U_min) <= 2 * D and (V_max - V_min) <= 2 * D:
            return True
        
        points_sorted_u = sorted(points, key=lambda p: p.u)
        n = len(points_sorted_u)
        if n == 0:
            return True
        
        prefix_u_min = [0] * n
        prefix_u_max = [0] * n
        prefix_v_min = [0] * n
        prefix_v_max = [0] * n
        prefix_u_min[0] = points_sorted_u[0].u
        prefix_u_max[0] = points_sorted_u[0].u
        prefix_v_min[0] = points_sorted_u[0].v
        prefix_v_max[0] = points_sorted_u[0].v
        for i in range(1, n):
            prefix_u_min[i] = min(prefix_u_min[i-1], points_sorted_u[i].u)
            prefix_u_max[i] = max(prefix_u_max[i-1], points_sorted_u[i].u)
            prefix_v_min[i] = min(prefix_v_min[i-1], points_sorted_u[i].v)
            prefix_v_max[i] = max(prefix_v_max[i-1], points_sorted_u[i].v)
        
        suffix_u_min = [0] * n
        suffix_u_max = [0] * n
        suffix_v_min = [0] * n
        suffix_v_max = [0] * n
        suffix_u_min[-1] = points_sorted_u[-1].u
        suffix_u_max[-1] = points_sorted_u[-1].u
        suffix_v_min[-1] = points_sorted_u[-1].v
        suffix_v_max[-1] = points_sorted_u[-1].v
        for i in range(n-2, -1, -1):
            suffix_u_min[i] = min(suffix_u_min[i+1], points_sorted_u[i].u)
            suffix_u_max[i] = max(suffix_u_max[i+1], points_sorted_u[i].u)
            suffix_v_min[i] = min(suffix_v_min[i+1], points_sorted_u[i].v)
            suffix_v_max[i] = max(suffix_v_max[i+1], points_sorted_u[i].v)
        
        for i in range(n):
            group1_u = prefix_u_max[i] - prefix_u_min[i]
            group1_v = prefix_v_max[i] - prefix_v_min[i]
            if i + 1 >= n:
                group2_u = 0
                group2_v = 0
            else:
                group2_u = suffix_u_max[i+1] - suffix_u_min[i+1]
                group2_v = suffix_v_max[i+1] - suffix_v_min[i+1]
            if (group1_u <= 2 * D and group1_v <= 2 * D and
                group2_u <= 2 * D and group2_v <= 2 * D):
                return True
        
        points_sorted_v = sorted(points, key=lambda p: p.v)
        prefix_u_min = [0] * n
        prefix_u_max = [0] * n
        prefix_v_min = [0] * n
        prefix_v_max = [0] * n
        prefix_u_min[0] = points_sorted_v[0].u
        prefix_u_max[0] = points_sorted_v[0].u
        prefix_v_min[0] = points_sorted_v[0].v
        prefix_v_max[0] = points_sorted_v[0].v
        for i in range(1, n):
            prefix_u_min[i] = min(prefix_u_min[i-1], points_sorted_v[i].u)
            prefix_u_max[i] = max(prefix_u_max[i-1], points_sorted_v[i].u)
            prefix_v_min[i] = min(prefix_v_min[i-1], points_sorted_v[i].v)
            prefix_v_max[i] = max(prefix_v_max[i-1], points_sorted_v[i].v)
        
        suffix_u_min = [0] * n
        suffix_u_max = [0] * n
        suffix_v_min = [0] * n
        suffix_v_max = [0] * n
        suffix_u_min[-1] = points_sorted_v[-1].u
        suffix_u_max[-1] = points_sorted_v[-1].u
        suffix_v_min[-1] = points_sorted_v[-1].v
        suffix_v_max[-1] = points_sorted_v[-1].v
        for i in range(n-2, -1, -1):
            suffix_u_min[i] = min(suffix_u_min[i+1], points_sorted_v[i].u)
            suffix_u_max[i] = max(suffix_u_max[i+1], points_sorted_v[i].u)
            suffix_v_min[i] = min(suffix_v_min[i+1], points_sorted_v[i].v)
            suffix_v_max[i] = max(suffix_v_max[i+1], points_sorted_v[i].v)
        
        for i in range(n):
            group1_u = prefix_u_max[i] - prefix_u_min[i]
            group1_v = prefix_v_max[i] - prefix_v_min[i]
            if i + 1 >= n:
                group2_u = 0
                group2_v = 0
            else:
                group2_u = suffix_u_max[i+1] - suffix_u_min[i+1]
                group2_v = suffix_v_max[i+1] - suffix_v_min[i+1]
            if (group1_u <= 2 * D and group1_v <= 2 * D and
                group2_u <= 2 * D and group2_v <= 2 * D):
                return True
        
        return False
    
    while low < high:
        mid = (low + high) // 2
        if is_possible(mid):
            high = mid
        else:
            low = mid + 1
    
    print(low)

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