题解 | 最大正方形

//注意i.j是行列，换成坐标就是（j,i）
//学到的数学方法：向量旋转公式
//对于多重循环更加清晰
#include<bits/stdc++.h>
using namespace std;
int main(){
    int n,len=0;
    cin>>n;
    vector<string>s(n);
    for(int i=0;i<n;i++){
        cin>>s[i];
    }
    vector<vector<int>>ans(n,vector<int>(n,0));
    int x1=0,y1=0,x2=0,y2=0,x3=0,y3=0,x4=0,y4=0;
    for(int i1=0;i1<n;i1++){
        for(int j1=0;j1<n;j1++){
            if(s[i1][j1]!='#')continue;
            for(int i2=i1;i2<n;i2++){
                for(int j2=0;j2<n;j2++){
                    if (i1 == i2 && j1 == j2) continue;
                    if(s[i2][j2]!='#')continue;
                    int dx=j2-j1,dy=i2-i1;
                    int j4=j1-dy,i4=i1+dx;
                    int j3=j2-dy,i3=i2+dx;
                    if(i3<0||i3>=n||i4<0||i4>=n||j3<0||j3>=n||j4<0||j4>=n)continue;
                    if(s[i3][j3]!='#'||s[i4][j4]!='#')continue;
                    int bian=dx*dx+dy*dy;
                    if(bian>len){
                        len=bian;
                        x1=i1;y1=j1;
                        x2=i2;y2=j2;
                        x3=i3;y3=j3;
                        x4=i4;y4=j4;
                    }
                }
            }
        }
    }
    cout<<x1+1<<" "<<y1+1<<endl;
    cout<<x2+1<<" "<<y2+1<<endl;
    cout<<x3+1<<" "<<y3+1<<endl;
    cout<<x4+1<<" "<<y4+1<<endl;
    return 0;
}