結果

問題 No.3759 Watch Fireworks
コンテスト
ユーザー Unbakedbread
提出日時 2026-10-11 12:18:21
言語 PyPy3
(7.3.23 + ACL)
コンパイル:
pypy3 -mpy_compile _filename_
実行:
pypy3 _filename_
結果
AC  
実行時間 508 ms / 2,000 ms
+ 105µs
コード長 690 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 64 ms
コンパイル使用メモリ 82,216 KB
実行使用メモリ 89,776 KB
最終ジャッジ日時 2026-10-11 12:18:36
合計ジャッジ時間 6,578 ms
ジャッジサーバーID
（参考情報） 		judge4_0 / judge1_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 47
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

N = int(input())
X, Y = [0] * N, [0] * N
for i in range(N):
	X[i], Y[i] = map(int, input().split())
	X[i], Y[i] = X[i] + Y[i], X[i] - Y[i]

Xmin, Xmax, Ymin, Ymax = min(X), max(X), min(Y), max(Y)
INF = 10 ** 18
def check(D):
	for x in (Xmin, Xmax - D):
		for y in (Ymin, Ymax - D):
			lx, rx, ly, ry = INF, -INF, INF, -INF
			for i in range(N):
				if x <= X[i] <= x + D and y <= Y[i] <= y + D:
					continue
				lx = min(lx, X[i])
				rx = max(rx, X[i])
				ly = min(ly, Y[i])
				ry = max(ry, Y[i])
			if rx - lx <= D and ry - ly <= D:
				return True
	return False

ng, ok = -1, 10 ** 10
while ok - ng > 1:
	mid = (ng + ok) // 2
	ok, ng = (mid, ng) if check(mid) else (ok, mid)
print(ok)
0