题解 | 最大正方形

#include <iostream>
#include <cmath>
using namespace std;

const int MAXN = 110;
char ch[MAXN][MAXN];
// 存储最终答案的四个顶点
int ans[4][2];
// 记录最大边长的平方（避免浮点运算，防止精度丢失）
int max_len_sq = 0;
int n;

// 更新答案的函数：确保记录最大边长的正方形
void update_ans(int x1, int y1, int x2, int y2, int x3, int y3, int x4, int y4) {
    // 计算边长的平方（AB向量的长度平方）
    int len_sq = (x2 - x1) * (x2 - x1) + (y2 - y1) * (y2 - y1);
    if (len_sq > max_len_sq) {
        max_len_sq = len_sq;
        ans[0][0] = x1; ans[0][1] = y1;
        ans[1][0] = x2; ans[1][1] = y2;
        ans[2][0] = x3; ans[2][1] = y3;
        ans[3][0] = x4; ans[3][1] = y4;
    }
}

int main() {
    cin >> n;
    // 读取矩阵（坐标从1开始）
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            cin >> ch[i][j];
        }
    }

    // 遍历所有可能的两个相邻顶点A(x1,y1)和B(x2,y2)
    for (int x1 = 1; x1 <= n; x1++) {
        for (int y1 = 1; y1 <= n; y1++) {
            // 只处理A点是#的情况
            if (ch[x1][y1] != '#') continue;
            for (int x2 = 1; x2 <= n; x2++) {
                for (int y2 = 1; y2 <= n; y2++) {
                    // 只处理B点是#且A≠B的情况（避免无效的0边长）
                    if (ch[x2][y2] != '#' || (x1 == x2 && y1 == y2)) continue;
                    
                    // 计算向量AB的dx和dy
                    int dx = x2 - x1;
                    int dy = y2 - y1;
                    
                    // 逆时针旋转90°，计算C和D的坐标
                    int x3 = x2 - dy;
                    int y3 = y2 + dx;
                    int x4 = x1 - dy;
                    int y4 = y1 + dx;
                    
                    // 验证C、D是否在矩阵范围内且为#
                    if (x3 >= 1 && x3 <= n && y3 >= 1 && y3 <= n &&
                        x4 >= 1 && x4 <= n && y4 >= 1 && y4 <= n &&
                        ch[x3][y3] == '#' && ch[x4][y4] == '#') {
                        update_ans(x1, y1, x2, y2, x3, y3, x4, y4);
                    }

                    // 顺时针旋转90°，计算C和D的坐标（覆盖另一方向的正方形）
                    x3 = x2 + dy;
                    y3 = y2 - dx;
                    x4 = x1 + dy;
                    y4 = y1 - dx;
                    
                    // 验证C、D是否在矩阵范围内且为#
                    if (x3 >= 1 && x3 <= n && y3 >= 1 && y3 <= n &&
                        x4 >= 1 && x4 <= n && y4 >= 1 && y4 <= n &&
                        ch[x3][y3] == '#' && ch[x4][y4] == '#') {
                        update_ans(x1, y1, x2, y2, x3, y3, x4, y4);
                    }
                }
            }
        }
    }

    // 输出四个顶点（题目允许任意顺序）
    for (int i = 0; i < 4; i++) {
        cout << ans[i][0] << " " << ans[i][1] << endl;
    }

    return 0;
}