結果

問題 No.3759 Watch Fireworks
コンテスト
ユーザー K2
提出日時 2026-10-09 23:20:21
言語 PyPy3
(7.3.23 + ACL)
コンパイル:
pypy3 -mpy_compile _filename_
実行:
pypy3 _filename_
結果
AC  
実行時間 829 ms / 2,000 ms
+ 754µs
コード長 1,293 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 62 ms
コンパイル使用メモリ 82,028 KB
実行使用メモリ 259,164 KB
最終ジャッジ日時 2026-10-09 23:20:30
合計ジャッジ時間 8,549 ms
ジャッジサーバーID
（参考情報） 		judge1_0 / judge3_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 47
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

N = int(input())
P = [tuple(map(int, input().split())) for _ in range(N)]
P = [(x + y, x - y) for x, y in P]

mi = min(P, key=lambda a: a[0])[0]
ma = max(P, key=lambda a: a[0])[0]

l = -1
r = 1 << 31

while r - l > 1:
    m = (l + r) // 2
    d = m / 2
    x1 = mi + d
    x2 = ma - d

    left = []
    both = []
    right = []
    ok = True
    for x, y in P:
        a = abs(x - x1) <= d
        b = abs(x - x2) <= d
        if a and b:
            both.append(y)
        elif a:
            left.append(y)
        elif b:
            right.append(y)
        else:
            ok = False
            break

    if left and max(left) - min(left) > 2 * d:
        ok = False
    if right and max(right) - min(right) > 2 * d:
        ok = False

    if not ok:
        l = m
        continue

    def bound(x: list[int]):
        return () if not x else (min(x) + d, max(x) - d)

    ok = False

    for y1 in bound(left) + bound(both):
        if ok:
            break
        for y2 in bound(right) + bound(both):
            if all(abs(y - y1) <= d for y in left) and all(abs(y - y2) <= d for y in right) and \
               all(min(abs(y - y1), abs(y - y2)) <= d for y in both):
                ok = True
                r = m
                break
    if not ok:
        l = m

print(r)
0