結果
| 問題 |
No.1998 Manhattan Restaurant
|
| ユーザー |
 gew1fw
|
| 提出日時 | 2025-06-12 21:13:37 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 8,466 bytes |
| コンパイル時間 | 378 ms |
| コンパイル使用メモリ | 82,432 KB |
| 実行使用メモリ | 125,696 KB |
| 最終ジャッジ日時 | 2025-06-12 21:15:15 |
| 合計ジャッジ時間 | 11,375 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 4 |
| other | AC * 3 WA * 28 |
ソースコード
import sys
def main():
input = sys.stdin.read().split()
idx = 0
N = int(input[idx])
idx += 1
points = []
u_list = []
v_list = []
for _ in range(N):
x = int(input[idx])
y = int(input[idx + 1])
idx += 2
u = x + y
v = x - y
u_list.append(u)
v_list.append(v)
points.append((u, v))
def is_possible(d):
# Check single square
u_low_all = max(u_i - d for u_i in u_list)
u_high_all = min(u_i + d for u_i in u_list)
v_low_all = max(v_i - d for v_i in v_list)
v_high_all = min(v_i + d for v_i in v_list)
if u_low_all <= u_high_all and v_low_all <= v_high_all:
return True
# Scenario a: leftmost u
u_min = min(u_list)
threshold = u_min + d
max_v_T_minus_d = -float('inf')
min_v_T_plus_d = float('inf')
has_T = False
for u_i, v_i in points:
if u_i <= threshold:
has_T = True
current_v_minus_d = v_i - d
current_v_plus_d = v_i + d
if current_v_minus_d > max_v_T_minus_d:
max_v_T_minus_d = current_v_minus_d
if current_v_plus_d < min_v_T_plus_d:
min_v_T_plus_d = current_v_plus_d
if has_T and max_v_T_minus_d <= min_v_T_plus_d:
# Check S
max_u_S_minus_d = -float('inf')
min_u_S_plus_d = float('inf')
max_v_S_minus_d = -float('inf')
min_v_S_plus_d = float('inf')
has_S = False
for u_i, v_i in points:
if u_i > threshold:
has_S = True
current_u_minus_d = u_i - d
current_u_plus_d = u_i + d
current_v_minus_d = v_i - d
current_v_plus_d = v_i + d
if current_u_minus_d > max_u_S_minus_d:
max_u_S_minus_d = current_u_minus_d
if current_u_plus_d < min_u_S_plus_d:
min_u_S_plus_d = current_u_plus_d
if current_v_minus_d > max_v_S_minus_d:
max_v_S_minus_d = current_v_minus_d
if current_v_plus_d < min_v_S_plus_d:
min_v_S_plus_d = current_v_plus_d
if not has_S:
return True
if has_S:
if (max_u_S_minus_d <= min_u_S_plus_d) and (max_v_S_minus_d <= min_v_S_plus_d):
return True
# Scenario b: rightmost u
u_max = max(u_list)
threshold = u_max - d
max_v_T_minus_d = -float('inf')
min_v_T_plus_d = float('inf')
has_T = False
for u_i, v_i in points:
if u_i >= threshold:
has_T = True
current_v_minus_d = v_i - d
current_v_plus_d = v_i + d
if current_v_minus_d > max_v_T_minus_d:
max_v_T_minus_d = current_v_minus_d
if current_v_plus_d < min_v_T_plus_d:
min_v_T_plus_d = current_v_plus_d
if has_T and max_v_T_minus_d <= min_v_T_plus_d:
# Check S
max_u_S_minus_d = -float('inf')
min_u_S_plus_d = float('inf')
max_v_S_minus_d = -float('inf')
min_v_S_plus_d = float('inf')
has_S = False
for u_i, v_i in points:
if u_i < threshold:
has_S = True
current_u_minus_d = u_i - d
current_u_plus_d = u_i + d
current_v_minus_d = v_i - d
current_v_plus_d = v_i + d
if current_u_minus_d > max_u_S_minus_d:
max_u_S_minus_d = current_u_minus_d
if current_u_plus_d < min_u_S_plus_d:
min_u_S_plus_d = current_u_plus_d
if current_v_minus_d > max_v_S_minus_d:
max_v_S_minus_d = current_v_minus_d
if current_v_plus_d < min_v_S_plus_d:
min_v_S_plus_d = current_v_plus_d
if not has_S:
return True
if has_S:
if (max_u_S_minus_d <= min_u_S_plus_d) and (max_v_S_minus_d <= min_v_S_plus_d):
return True
# Scenario c: bottommost v
v_min = min(v_list)
threshold = v_min + d
max_u_T_minus_d = -float('inf')
min_u_T_plus_d = float('inf')
has_T = False
for u_i, v_i in points:
if v_i <= threshold:
has_T = True
current_u_minus_d = u_i - d
current_u_plus_d = u_i + d
if current_u_minus_d > max_u_T_minus_d:
max_u_T_minus_d = current_u_minus_d
if current_u_plus_d < min_u_T_plus_d:
min_u_T_plus_d = current_u_plus_d
if has_T and max_u_T_minus_d <= min_u_T_plus_d:
# Check S
max_v_S_minus_d = -float('inf')
min_v_S_plus_d = float('inf')
max_u_S_minus_d = -float('inf')
min_u_S_plus_d = float('inf')
has_S = False
for u_i, v_i in points:
if v_i > threshold:
has_S = True
current_v_minus_d = v_i - d
current_v_plus_d = v_i + d
current_u_minus_d = u_i - d
current_u_plus_d = u_i + d
if current_v_minus_d > max_v_S_minus_d:
max_v_S_minus_d = current_v_minus_d
if current_v_plus_d < min_v_S_plus_d:
min_v_S_plus_d = current_v_plus_d
if current_u_minus_d > max_u_S_minus_d:
max_u_S_minus_d = current_u_minus_d
if current_u_plus_d < min_u_S_plus_d:
min_u_S_plus_d = current_u_plus_d
if not has_S:
return True
if has_S:
if (max_u_S_minus_d <= min_u_S_plus_d) and (max_v_S_minus_d <= min_v_S_plus_d):
return True
# Scenario d: topmost v
v_max = max(v_list)
threshold = v_max - d
max_u_T_minus_d = -float('inf')
min_u_T_plus_d = float('inf')
has_T = False
for u_i, v_i in points:
if v_i >= threshold:
has_T = True
current_u_minus_d = u_i - d
current_u_plus_d = u_i + d
if current_u_minus_d > max_u_T_minus_d:
max_u_T_minus_d = current_u_minus_d
if current_u_plus_d < min_u_T_plus_d:
min_u_T_plus_d = current_u_plus_d
if has_T and max_u_T_minus_d <= min_u_T_plus_d:
# Check S
max_v_S_minus_d = -float('inf')
min_v_S_plus_d = float('inf')
max_u_S_minus_d = -float('inf')
min_u_S_plus_d = float('inf')
has_S = False
for u_i, v_i in points:
if v_i < threshold:
has_S = True
current_v_minus_d = v_i - d
current_v_plus_d = v_i + d
current_u_minus_d = u_i - d
current_u_plus_d = u_i + d
if current_v_minus_d > max_v_S_minus_d:
max_v_S_minus_d = current_v_minus_d
if current_v_plus_d < min_v_S_plus_d:
min_v_S_plus_d = current_v_plus_d
if current_u_minus_d > max_u_S_minus_d:
max_u_S_minus_d = current_u_minus_d
if current_u_plus_d < min_u_S_plus_d:
min_u_S_plus_d = current_u_plus_d
if not has_S:
return True
if has_S:
if (max_u_S_minus_d <= min_u_S_plus_d) and (max_v_S_minus_d <= min_v_S_plus_d):
return True
return False
# Binary search
left = 0
right = 10**18
answer = 10**18
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()