题解 | #最大正方形#

因为所以直接枚举。

先用找出两个顶点，再计算其余顶点。

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

int main() {
    int n;
    cin>>n;
    vector<string>a(n);
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    vector<pair<int,int>>sharp;
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
        //记录可能的顶点
            if(a[i][j]=='#')sharp.push_back({i,j});
        }
    }
    int maxlen2=-1;
    vector<pair<int,int>>sqare(4);
    int cnt=sharp.size();
    for(int i=0;i<cnt;i++){
        int x1=sharp[i].first,y1=sharp[i].second;
        for(int j=i+1;j<cnt;j++){
            int x2=sharp[j].first,y2=sharp[j].second;
            int dx=x2-x1,dy=y2-y1;
            //计算并判断剩余两个顶点是否存在
            if((x1+x2-dy)%2!=0||(x1+x2+dy)%2!=0||(y1+y2-dx)%2!=0||(y1+y2+dx)%2!=0)continue;
            int x3=(x1+x2-dy)/2,y3=(y1+y2+dx)/2;
            int x4=(x1+x2+dy)/2,y4=(y1+y2-dx)/2;
            if(x3<0||x3>=n||y3<0||y3>=n||x4<0||x4>=n||y4<0||y4>=n)continue;
            if(a[x3][y3]!='#'||a[x4][y4]!='#')continue;
            int len2=dx*dx+dy*dy;
            if(len2>maxlen2){
                maxlen2=len2;
                sqare[0]={x1+1,y1+1};
                sqare[1]={x2+1,y2+1};
                sqare[2]={x3+1,y3+1};
                sqare[3]={x4+1,y4+1};
            }
        }
    }
    //直接用循环输出的话，顺序与样例不同，需要手动控制顺序
    int i=0;
    cout<<sqare[i].first<<" "<<sqare[i].second<<endl;
    i=2;
    cout<<sqare[i].first<<" "<<sqare[i].second<<endl;
    i=1;
    cout<<sqare[i].first<<" "<<sqare[i].second<<endl;
    i=3;
    cout<<sqare[i].first<<" "<<sqare[i].second<<endl;
    return 0;
}