麦田选址¶
- 参考时间限制：0.5 秒（参考环境：评测环境与性能；仅供预估）
- 实际时间限制：标准程序在目标评测环境中处理最慢正式测试文件的基准时间的 2 倍，按 0.5 秒的倍数向上取整；若平台仅支持更粗的粒度，再向上取整到平台可设置值。
- 内存限制：128 MB
背景故事¶
村长计划开辟一片正方形麦田，让它成为村庄的一处整齐景观。候选区域内已有一些建筑，麦田不能占用这些位置。请找出能够种植的最大正方形。
形式化问题描述¶
给定一个 \(n\) 行 \(m\) 列的网格，以及 \(k\) 条建筑位置记录 \((x_i,y_i)\) .记录可能重复，同一位置重复出现仍只表示该格有建筑。
选择连续的 \(s\) 行和连续的 \(s\) 列作为麦田，要求其中没有任何建筑。求最大的整数边长 \(s\) ；如果没有可用方格，输出 \(0\) .
输入格式¶
第一行三个整数 \(n,m,k\) .接下来 \(k\) 行，每行两个整数 \(x_i,y_i\) ，表示第 \(x_i\) 行、第 \(y_i\) 列有建筑。
输出格式¶
输出一个整数，表示最大边长。
样例 1¶
输入¶
5 7 3
1 1
1 3
5 7
输出¶
4
解释¶
选择第 \(2\) 到 \(5\) 行、第 \(2\) 到 \(5\) 列，可以得到边长为 \(4\) 的麦田。边长为 \(5\) 时必须覆盖全部五行，而任意连续五列都会包含至少一个建筑。
图 1：带叉号的格子表示建筑，粗框和浅色区域表示一块合法麦田。
样例 2¶
输入¶
2 2 4
1 1
1 2
2 1
1 2
输出¶
1
解释¶
位置 \((1,2)\) 被重复记录，实际只有三个格子被占用，剩余一格可以种植。
样例 3¶
输入¶
2 2 4
1 1
1 2
2 1
2 2
输出¶
0
解释¶
四个格子都有建筑，答案为零。
数据范围与保证¶
- \(1\le n,m\le100000\) ，\(0\le k\le200\) .
- \(1\le x_i\le n\) ，\(1\le y_i\le m\) ；建筑记录允许重复。
数据分组¶
| 分值比例 | 额外条件 |
|---|---|
| 100% | 无额外条件 |