結果
問題 | No.1998 Manhattan Restaurant |
ユーザー |
![]() |
提出日時 | 2024-12-02 14:11:01 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 204 ms / 2,000 ms |
コード長 | 1,146 bytes |
コンパイル時間 | 259 ms |
コンパイル使用メモリ | 82,004 KB |
実行使用メモリ | 82,744 KB |
最終ジャッジ日時 | 2024-12-02 14:11:07 |
合計ジャッジ時間 | 5,077 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 31 |
ソースコード
import sysinput = sys.stdin.readlineINF = 10 ** 18N = int(input())P = []for _ in [0] * N:x, y = map(int, input().split())P.append((x + y, x - y))max_x = max_y = -INFmin_x = min_y = INFfor x, y in P:if(max_x < x):max_x = xif(max_y < y):max_y = yif(min_x > x):min_x = xif(min_y > y):min_y = ydef func(mid):mid *= 2block = [[0] * 2 for _ in [0] * 2]for x, y in P:if((x < max_x - mid and x > min_x + mid) or (y < max_y - mid and y > min_y + mid)):return Falseif(x < max_x - mid and y < max_y - mid):block[0][0] = 1if(x > min_x + mid and y < max_y - mid):block[1][0] = 1if(x < max_x - mid and y > min_y + mid):block[0][1] = 1if(x > min_x + mid and y > min_y + mid):block[1][1] = 1if((block[0][0] | block[1][1]) == 0 or (block[0][1] | block[1][0]) == 0):return Truereturn Falseok = 2 * 10 ** 9 + 1ng = -1while(abs(ok - ng) > 1):mid = (ok + ng) // 2if func(mid):ok = midelse:ng = midprint(ok)