题解 | 最大正方形

#include<bits/stdc++.h>
using namespace std;
int n;
char ch[110][110];
int ans[4][2]; 
int main(){
    cin>>n;
    for (int i=1;i<=n;i++)
        for (int j=1;j<=n;j++)
            cin>>ch[i][j];
    for (int i=0;i<4;i++)
        ans[i][0]=ans[i][1]=0;

    int x1,y1,x2,y2,x3,y3,x4,y4;
    double len_sq,max_len_sq=0;
    for(x1=1;x1<=n;x1++){
        for(y1=1;y1<=n;y1++){
            if(ch[x1][y1]!='#')continue;

            for(x2=1;x2<=n;x2++){
                for(y2=1;y2<=n;y2++){
                    if(ch[x2][y2]!='#')continue;
                    if(x1==x2&&y1==y2)continue; 
                    int dx=x2-x1;
                    int dy=y2-y1;
                    x3=x1-dy;
                    y3=y1+dx;
                    x4=x2-dy;
                    y4=y2+dx;

                    // 检查顶点是否在矩阵范围内
                    if(x3<1||x3>n||y3<1||y3>n)continue;
                    if(x4<1||x4>n||y4<1||y4>n)continue;

                    // 检查另外两个顶点是否为 '#'
                    if(ch[x3][y3]=='#'&&ch[x4][y4]=='#'){
                        len_sq=dx*dx+dy*dy;
                        // 更新最大正方形
                        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;
                        }
                    }
                }
            }
        }
    }
    for(int i=0;i<4;i++){
        cout<<ans[i][0]<<" "<<ans[i][1]<<endl;
    }
    return 0;
}