結果

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

ソースコード

diff # 

import sys

def main():
    input = sys.stdin.read().split()
    idx = 0
    N = int(input[idx])
    idx += 1
    houses = []
    for _ in range(N):
        x = int(input[idx])
        y = int(input[idx+1])
        idx += 2
        u = x + y
        v = x - y
        houses.append((u, v))
    
    if N == 0:
        print(0)
        return
    
    left = 0
    right = 2 * 10**18  # A large enough upper bound
    
    def is_possible(D):
        # Check if all can be covered by one restaurant
        min_u_plus = max_u_minus = houses[0][0]
        max_u_plus = min_u_minus = houses[0][0]
        min_v_plus = max_v_minus = houses[0][1]
        max_v_plus = min_v_minus = houses[0][1]
        for u, v in houses:
            u_min = u - D
            u_max = u + D
            if u_min > max_u_minus:
                max_u_minus = u_min
            if u_max < min_u_plus:
                min_u_plus = u_max
            v_min = v - D
            v_max = v + D
            if v_min > max_v_minus:
                max_v_minus = v_min
            if v_max < min_v_plus:
                min_v_plus = v_max
        if max_u_minus <= min_u_plus and max_v_minus <= min_v_plus:
            return True
        
        # Generate candidates
        candidates = []
        min_u_plus_val = min(u + D for u, v in houses)
        for i in range(N):
            if houses[i][0] + D == min_u_plus_val:
                candidates.append(i)
                break
        
        max_u_minus_val = max(u - D for u, v in houses)
        for i in range(N):
            if houses[i][0] - D == max_u_minus_val:
                candidates.append(i)
                break
        
        min_v_plus_val = min(v + D for u, v in houses)
        for i in range(N):
            if houses[i][1] + D == min_v_plus_val:
                candidates.append(i)
                break
        
        max_v_minus_val = max(v - D for u, v in houses)
        for i in range(N):
            if houses[i][1] - D == max_v_minus_val:
                candidates.append(i)
                break
        
        seen = set()
        unique_candidates = []
        for c in candidates:
            if c not in seen:
                seen.add(c)
                unique_candidates.append(c)
        
        for idx_c in unique_candidates:
            u_a, v_a = houses[idx_c]
            u1_low = u_a - D
            u1_high = u_a + D
            v1_low = v_a - D
            v1_high = v_a + D
            
            S = []
            for i in range(N):
                u, v = houses[i]
                cond_u = (u - D <= u1_high) and (u + D >= u1_low)
                cond_v = (v - D <= v1_high) and (v + D >= v1_low)
                if cond_u and cond_v:
                    S.append(i)
            
            if not S:
                continue
            
            s_u_low = max(houses[i][0] - D for i in S)
            s_u_high = min(houses[i][0] + D for i in S)
            s_v_low = max(houses[i][1] - D for i in S)
            s_v_high = min(houses[i][1] + D for i in S)
            
            if s_u_low > s_u_high or s_v_low > s_v_high:
                continue
            
            T = [i for i in range(N) if i not in S]
            if not T:
                return True
            
            t_u_low = max(houses[i][0] - D for i in T)
            t_u_high = min(houses[i][0] + D for i in T)
            t_v_low = max(houses[i][1] - D for i in T)
            t_v_high = min(houses[i][1] + D for i in T)
            
            if t_u_low <= t_u_high and t_v_low <= t_v_high:
                return True
        
        return False
    
    answer = 0
    while left <= right:
        mid = (left + right) // 2
        if is_possible(mid):
            answer = mid
            right = mid - 1
        else:
            left = mid + 1
    print(answer)

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