题目分析

我们需要在给定的二进制矩阵中找到最大的圆形区域，使得：

1. 圆盘完全在平面内
2. 圆盘覆盖的所有点对应的矩阵位置都是 1
3. 圆心坐标为整数
4. 半径平方取整后最大

---

核心思路

1. 问题转化

对于每个可能的圆心 (x, y)，我们需要找到最大的半径 r，使得以 (x, y) 为圆心、半径为 r 的圆盘完全位于 1 的区域中。

由于圆心坐标是整数，我们可以将问题转化为：对于每个可能的圆心，找到它到最近的 0 的距离。

---

2. 关键观察

• 圆的半径平方必须是整数（因为圆心和障碍点都是整数坐标）
• 我们需要找到每个点到最近障碍物的距离，然后取最大值
• 障碍物是矩阵中为 0 的位置

---

3. 算法设计

3.1 预处理垂直距离

代码中定义了：

• up[i][j]：从位置 (i, j) 向上最近的障碍物行号
• dwn[i][j]：从位置 (i, j) 向下最近的障碍物行号

这样对于每一列，我们可以快速知道任意行到垂直方向最近障碍物的距离。

3.2 凸包优化

对于每一行 y，我们考虑该行上所有点 (x, y) 到障碍物的距离。问题转化为：对于每个 x，找到最小的 (x - x₀)² + (y - y₀)²，其中 (x₀, y₀) 是障碍物。

使用凸包技巧（类似于斜率优化）来高效计算：

• 维护一个下凸包
• 对于每个 x，在凸包上二分找到最优的 x₀
• 时间复杂度从 O(M²) 降为 O(M)

3.3 对称处理

代码分别处理原矩阵和翻转后的矩阵：

• ans[0]：原矩阵的结果
• ans[1]：水平翻转后的结果

这样可以同时考虑左右两个方向的障碍物。

---

4. 具体实现

4.1 距离计算

int dist(int x, int y, int xx, int yy) {
    return sqr(x - xx) + sqr(y - yy);
}

4.2 凸包维护

while (tail < head && slope(dq[tail + 1], dq[tail]) >= slope(dq[tail], i))
    tail++;
dq[--tail] = i;

4.3 最终选择

在所有可能的圆心中：

1. 优先选择半径平方最大的
2. 半径相同时选择 y 坐标最小的
3. y 坐标相同时选择 x 坐标最小的

---

复杂度分析

• 预处理垂直距离：O(N × M)
• 每行的凸包计算：O(M)
• 总复杂度：O(N × M)
• 空间复杂度：O(N × M)

对于 N, M ≤ 3000 完全可行。

---

样例验证

样例 1

输入：
5 6
011110
111110
011111
111111
011110

输出：
3 2 4

解释：以 (3, 2) 为圆心，半径平方为 4 的圆是最大的可行圆。

样例 2

输入：
3 3
010
101
010

输出：
0 0 0

解释：没有半径为正整数的圆。

---

算法标签

• 凸包优化 (Convex Hull Optimization)
• 最近障碍物距离 (Nearest Obstacle Distance)
• 几何处理 (Geometric Processing)
• 动态规划 (Dynamic Programming)

---

总结

本题通过巧妙的预处理和凸包优化，将看似复杂的几何问题转化为高效的可计算问题。核心在于利用矩阵的特性和凸包的性质，在 O(N × M) 时间内找到最优解。