配点 : 600 点
問題文
H 行 W 方格列,每列都填充有黑色或白色。从上面 i 行,从左起 j 标记列中的方块 它被称为 (i, j) 。
质量 (a_i, b_i) (1 \leq i \leq K) 被漆成白色;其他 H \times W - K 方块被漆成黑色。 大于或等于
1 的整数
网格的大小是相对于 k 包含 k 的 N 表示满足以下条件的整数:
表示 i, j 存在。
- 质量 (i + t, j) (0 \leq t < k) 全黑
- 质量 (i + t, j + t) (0 \leq t < k) 全黑
- 质量 (i + t, j + k - 1) (0 \leq t < k) 全黑
但是,与此条件相关的所有方块 H 行 W 必须包含在列网格中。
包含在此方块中
求 N 的最大尺寸。然而,什么尺寸
如果它不包含 N ,0 。
制約
- 1 \leq H, W \leq 3000
- 0 \leq K \leq \mathrm{min}(H \times W, 2 \times 10^5)
- 1 \leq a_i \leq H
- 1 \leq b_i \leq W
- (a_i, b_i) \neq (a_j, b_j) (i \neq j)
- 所有输入均为整数
入力
输入将以以下格式从标准输入提供。
H W K a_1 b_1 a_2 b_2 : a_K b_K
出力
包含在网格中
打印 N 的最大尺寸。
入力例 1
3 4 2 1 3 3 3
出力例 1
3
网格处于以下状态。 (# 是黑色,. 被涂成白色)
##.# #### ##.#
此时,i = 1, j = 2 如果
由于 k = 3 满足条件,因此该正方形的大小为
包含 3 的 N ,这是最大值。
入力例 2
2 2 4 2 1 1 1 1 2 2 2
出力例 2
0
网格处于以下状态。
.. ..
哪个尺寸? N 不包括在内,所以0 。
入力例 3
2 2 2 1 1 2 2
出力例 3
1
网格处于以下状态。
.# #.
i = 2, j = 1 或 如果 i = 1, j = 2 如果 由于 k = 1 满足条件。
入力例 4
4 4 5 2 3 1 3 4 2 4 3 3 2
出力例 4
4
网格处于以下状态。
##.# ##.# #.## #..#