麦田选址：题解¶

解法比较¶

出题人解法枚举障碍点与田地边界给出的两条水平支撑线，在这个条带内按横坐标扫描阻挡点，取相邻阻挡之间最大的正方形边长。最优空正方形可移动或扩张，直到受到边界或障碍限制，因此这些候选条带足够；边界接触的判定按题意处理。

Codex（GPT-6）的实现枚举竖直支撑线并扫描纵向间隙。交换横纵坐标即可得到上述水平扫描，同一支撑线证明适用于两种方向。障碍数为 \(k\) 时，两者均为 \(O(k^3)\) 时间、\(O(k)\) 空间。

枚举左右边界¶

网格很大，但建筑数量很少。把建筑的列坐标与虚拟边界 \(0,m+1\) 合并、排序并去重，得到候选边界集合。枚举其中两个数 \(l<r\) ，考虑列号严格位于两者之间的条带，宽度为 \(w=r-l-1\) .

只取位于该条带内部的建筑，按行坐标排序，并在两端补上 \(0,n+1\) .任意相邻行坐标 \(a,b\) 之间没有条带内的建筑，因此形成高 \(h=b-a-1\) 、宽 \(w\) 的空矩形，可放入边长 \(\min(h,w)\) 的正方形。

预先将全部建筑按行排序；枚举一对列边界后，只需顺序扫描并过滤，无需重新排序。重复建筑只会产生空的间隙，不影响最大答案。

正确性¶

算法考察的每个空矩形都没有建筑，取其中较短边长的正方形一定合法。

反过来，考虑任意合法正方形。保持其行范围不变，尽量向左右扩展成空矩形，直到网格边界或该行范围内某个建筑将扩展阻挡。因此左右外侧边界都属于枚举的候选集合。对这一对边界扫描建筑时，必有一个相邻建筑行之间的空隙包含原正方形的全部行；条带宽度和该空隙高度都至少为原正方形边长。算法必然得到不小于它的答案。结合可行性，最终答案最优。

复杂度¶

候选列边界至多 \(k+2\) 个，每对边界扫描 \(k\) 个建筑。时间为 \(O((k+1)^3)\) ，空间为 \(O(k+1)\) ；这一写法也包含 \(k=0\) 的情形。网格尺寸只影响坐标和答案，不需要建立 \(n\times m\) 数组。