結果
| 問題 |
No.1998 Manhattan Restaurant
|
| ユーザー |
 lam6er
|
| 提出日時 | 2025-03-31 17:56:11 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 6,597 bytes |
| コンパイル時間 | 252 ms |
| コンパイル使用メモリ | 82,848 KB |
| 実行使用メモリ | 252,620 KB |
| 最終ジャッジ日時 | 2025-03-31 17:57:34 |
| 合計ジャッジ時間 | 14,337 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 4 |
| other | AC * 10 WA * 21 |
ソースコード
import sys
def main():
N = int(sys.stdin.readline())
points = []
for _ in range(N):
X, Y = map(int, sys.stdin.readline().split())
u = X + Y
v = X - Y
points.append((u, v))
if N == 1:
print(0)
return
# Pre-sort the points by u and by v
sorted_u = sorted(points, key=lambda x: x[0])
sorted_v = sorted(points, key=lambda x: x[1])
# Compute global min and max for initial checks
min_u_all = sorted_u[0][0]
max_u_all = sorted_u[-1][0]
min_v_all = sorted_v[0][1]
max_v_all = sorted_v[-1][1]
# Calculate the maximum possible D for a single restaurant scenario
def compute_D_single():
span_u = max_u_all - min_u_all
span_v = max_v_all - min_v_all
return max(span_u // 2, span_v // 2)
D_single = compute_D_single()
# Binary search setup
low = 0
high = D_single
answer = high
def is_possible(D):
# Check if all points can be covered by a single square
if (max_u_all - min_u_all) <= 2 * D and (max_v_all - min_v_all) <= 2 * D:
return True
# Check splits along sorted_u
n = len(sorted_u)
# Precompute prefix arrays for u sorted points
prefix_min_u = [0] * n
prefix_max_u = [0] * n
prefix_min_v = [0] * n
prefix_max_v = [0] * n
current_min_u = sorted_u[0][0]
current_max_u = current_min_u
current_min_v = sorted_u[0][1]
current_max_v = current_min_v
prefix_min_u[0] = current_min_u
prefix_max_u[0] = current_max_u
prefix_min_v[0] = current_min_v
prefix_max_v[0] = current_max_v
for i in range(1, n):
u, v = sorted_u[i]
current_min_u = min(current_min_u, u)
current_max_u = max(current_max_u, u)
current_min_v = min(current_min_v, v)
current_max_v = max(current_max_v, v)
prefix_min_u[i] = current_min_u
prefix_max_u[i] = current_max_u
prefix_min_v[i] = current_min_v
prefix_max_v[i] = current_max_v
# Precompute suffix arrays for u sorted points
suffix_min_u = [0] * n
suffix_max_u = [0] * n
suffix_min_v = [0] * n
suffix_max_v = [0] * n
current_min_u = sorted_u[-1][0]
current_max_u = current_min_u
current_min_v = sorted_u[-1][1]
current_max_v = current_min_v
suffix_min_u[-1] = current_min_u
suffix_max_u[-1] = current_max_u
suffix_min_v[-1] = current_min_v
suffix_max_v[-1] = current_max_v
for i in range(n-2, -1, -1):
u, v = sorted_u[i]
current_min_u = min(current_min_u, u)
current_max_u = max(current_max_u, u)
current_min_v = min(current_min_v, v)
current_max_v = max(current_max_v, v)
suffix_min_u[i] = current_min_u
suffix_max_u[i] = current_max_u
suffix_min_v[i] = current_min_v
suffix_max_v[i] = current_max_v
# Check all possible splits in u-sorted order
for i in range(n-1):
left_span_u = prefix_max_u[i] - prefix_min_u[i]
left_span_v = prefix_max_v[i] - prefix_min_v[i]
if left_span_u > 2 * D or left_span_v > 2 * D:
continue
right_span_u = suffix_max_u[i+1] - suffix_min_u[i+1]
right_span_v = suffix_max_v[i+1] - suffix_min_v[i+1]
if right_span_u <= 2 * D and right_span_v <= 2 * D:
return True
# Check splits along sorted_v
# Precompute prefix arrays for v sorted points
prefix_min_u_v = [0] * n
prefix_max_u_v = [0] * n
prefix_min_v_v = [0] * n
prefix_max_v_v = [0] * n
current_min_u_v = sorted_v[0][0]
current_max_u_v = current_min_u_v
current_min_v_v = sorted_v[0][1]
current_max_v_v = current_min_v_v
prefix_min_u_v[0] = current_min_u_v
prefix_max_u_v[0] = current_max_u_v
prefix_min_v_v[0] = current_min_v_v
prefix_max_v_v[0] = current_max_v_v
for i in range(1, n):
u, v = sorted_v[i]
current_min_u_v = min(current_min_u_v, u)
current_max_u_v = max(current_max_u_v, u)
current_min_v_v = min(current_min_v_v, v)
current_max_v_v = max(current_max_v_v, v)
prefix_min_u_v[i] = current_min_u_v
prefix_max_u_v[i] = current_max_u_v
prefix_min_v_v[i] = current_min_v_v
prefix_max_v_v[i] = current_max_v_v
# Precompute suffix arrays for v sorted points
suffix_min_u_v = [0] * n
suffix_max_u_v = [0] * n
suffix_min_v_v = [0] * n
suffix_max_v_v = [0] * n
current_min_u_v = sorted_v[-1][0]
current_max_u_v = current_min_u_v
current_min_v_v = sorted_v[-1][1]
current_max_v_v = current_min_v_v
suffix_min_u_v[-1] = current_min_u_v
suffix_max_u_v[-1] = current_max_u_v
suffix_min_v_v[-1] = current_min_v_v
suffix_max_v_v[-1] = current_max_v_v
for i in range(n-2, -1, -1):
u, v = sorted_v[i]
current_min_u_v = min(current_min_u_v, u)
current_max_u_v = max(current_max_u_v, u)
current_min_v_v = min(current_min_v_v, v)
current_max_v_v = max(current_max_v_v, v)
suffix_min_u_v[i] = current_min_u_v
suffix_max_u_v[i] = current_max_u_v
suffix_min_v_v[i] = current_min_v_v
suffix_max_v_v[i] = current_max_v_v
# Check all possible splits in v-sorted order
for i in range(n-1):
left_span_u = prefix_max_u_v[i] - prefix_min_u_v[i]
left_span_v = prefix_max_v_v[i] - prefix_min_v_v[i]
if left_span_u > 2 * D or left_span_v > 2 * D:
continue
right_span_u = suffix_max_u_v[i+1] - suffix_min_u_v[i+1]
right_span_v = suffix_max_v_v[i+1] - suffix_min_v_v[i+1]
if right_span_u <= 2 * D and right_span_v <= 2 * D:
return True
return False
# Perform binary search
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()