题意

• 给定一个由*和#构成的正方形矩阵，求其中以#为顶点的最大正方形，输出四个顶点坐标

思路

• 两个点确定一个正方形，三个点确定一个长方形，枚举所有的两个#，check当前两个#构造出的另外两个顶点是否为#，通过边长比较正方形大小
• 注意：计算几何中尽可能避免硬解方程组，多考虑向量和三角函数，本题使用三角推导另两个点最为便捷
• 附图：

AC代码

#include<bits/stdc++.h>
using namespace std;
char mp[120][120];
long long l=0;
vector<int>ans(8);
int n;
void check(int x,int y){
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(mp[i][j]=='#'){
                int dx=i-x,dy=j-y;
                if(x+dy<=0||x+dy>n||y-dx<=0||y-dx>n||i+dy<=0||i+dy>n||j-dx<=0||j-dx>n)continue;
                if(mp[x+dy][y-dx]=='#'&&mp[i+dy][j-dx]=='#'&&1ll*dx*dx+dy*dy>l){
                    l=dx*dx+dy*dy;
                    ans={x,y,i,j,x+dy,y-dx,i+dy,j-dx};
                }
            }
        }
    }
}
int main(){
    scanf("%d ",&n);
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            scanf("%c",&mp[i][j]);
        }
        getchar();
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(mp[i][j]=='#'){
                check(i,j);
            }
        }
    }
    for(int i=0;i<8;i++){
        printf("%d ",ans[i]);
        if(i%2) printf("\n");
    }
    return 0;
}

随想

• 数学感觉还是很差，对向量的应用很难一下理解，听到雨巨用的对角线，推了半天式子还是对不上给的代码，最后发现使用的是相邻两点，难以评价-_-