← 返回题目列表

AtCoder · nikkei2019_2_final_c

C. 最大N

中文机器翻译题面 查看原题

配点 : 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

网格处于以下状态。

##.#  
##.#  
#.##  
#..#