思路

枚举所有两个 # 点，把它们作为正方形的一条边，推算出另外两个顶点，检查是否也是 #，记录边长最大的那个。

步骤

  1. 收集所有 # 的坐标。
  2. 枚举两个不同的 # 点 (x1,y1) 和 (x2,y2)，计算 dx = x2-x1，dy = y2-y1。
  3. 得到另外两个候选顶点： 以及
  4. 检查这两组点是否都在网格内且为 #。
  5. 若成立，计算边长平方 dx²+dy²，更新最大边长对应的四个顶点。
  6. 输出最终找到的四个顶点坐标。

复杂度

  • O(m²)，m 为 # 的数量，n≤100 时足够快。
#include <iostream>
#include <cmath>
#include <vector>
using namespace std;

struct Point{
    int x = 0, y = 0;
    Point(int x, int y){
        this->x = x;
        this->y = y;
    }
};

int main() {
    int n;cin>>n;
    vector<pair<int, int>> sharps;
    vector<vector<char>> mp(110, vector<char>(110,'0'));
    for(int i = 1;i <= n;++i){
        for(int j = 1;j <= n;++j ){
            cin>>mp[i][j];
            if(mp[i][j] == '#'){
                sharps.emplace_back(i, j);
            }
        }
    }
    
  	//判断点是否合法
    auto check0 = [&](Point a) -> bool{
        if(a.x > n || a.x < 1 || a.y > n || a.y < 1) return false;
        if(mp[a.x][a.y] != '#') return false;
        return true;
    };
  	//检查点对是否合法
    auto check = [&](Point a, Point b) -> bool{
	  	//两个点是否都合法
        if(check0(a) == false || check0(b) == false) return false;
        return true;
    };
    auto dis = [&](Point a, Point b) ->double{
        double d = sqrtl((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
        return d;
    };

    double ans = 0;
    vector<Point> res(4, {0, 0});
    for(int i = 0;i < sharps.size();++i){
        int x1 = sharps[i].first, y1 = sharps[i].second;
        for(int j = i + 1;j < sharps.size();++j){
            int x2 = sharps[j].first, y2 = sharps[j].second;
            Point p1 = Point(x1, y1);
            Point p2 = Point(x2, y2);
            
            int dx = x2 - x1;
            int dy = y2 - y1;
            //待检测点对
            //p1、p2是正方形的同一条边上的点
            Point p3(x1 - dy, y1 + dx);
            Point p4(x2 - dy, y2 + dx);

            Point p5(x1 + dy, y1 - dx);
            Point p6(x2 + dy, y2 - dx);
            
            if(check(p3, p4) && dis(p1, p2) > ans){
                res = {p1, p2, p3, p4};
                ans = dis(p1, p2);
            }
            if(check(p5, p6) && dis(p5, p6) > ans){
                res = {p1, p2, p5, p6};
                ans = dis(p5, p6);
            }
        }
    }
    for(auto i : res){
        cout<<i.x<<" "<<i.y<<endl;
    }
}
// 64 位输出请用 printf("%lld")