#include <iostream>
using namespace std;
/*
题中坐标从1开始,但操作时i,j均从0开始,在最后输出时对结果加一即可
先把所有的字符储存至cs[n][n]
然后开始遍历
先遍历到第一个#号,然后去找第二个#号,把这两个#号作为正方形的两个顶点
根据这两个顶点,通过计算得到第三和第四个"顶点"的位置,并检验此四点是否是正方形
先判断第三和第四个"顶点"是否在范围内
若在,则下一步,否则,跳过本次,找下一个第二个顶点
然后判断第三和第四个"顶点"是否是#
若是,则下一步,否则,跳过本次,找下一个第二个顶点
如果第三和第四个"顶点"是#,那么说明这四个点确实是正方形的四个顶点
再接着计算这个正方形的边长
(这里仅计算(x1-x2)^2 + (y1-y2)^2,考虑到浮点数精度问题,不再开方)
如果这个正方形的边长 大于 已经找到的最大的正方形的边长
记录该正方形的四个顶点的位置,以及该正方形的边长
继续寻找下一个正方形
最后,把得到的正方形的四个顶点按规则输出,记得+1(题中i,j从1开始编号)
*/
void solve() {
int n;
cin >> n;
char cs[n][n];
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cin >> cs[i][j];
}
}
// 初始值
int max_leng_pow = -1;
int ans[4][2] = {-1,-1,-1,-1,
-1,-1,-1,-1};
// Δi 和 Δj
int di=0;
int dj=0;
// 遍历得到第一个顶点坐标(i,j)
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
// 如果(i,j)是正方形的一个顶点,那么继续
if(cs[i][j]=='#'){
// 遍历得到正方形的第二个顶点坐标(i_,j_)
for(int i_=i;i_<n;i_++){
for(int j_=j;j_<n;j_++){
// 如果(i_,j_)是正方形的第二个顶点,那么继续
if (cs[i_][j_]=='#') {
di = i_ - i;
dj = j_ - j;
// 检查第三个,第四个"顶点"是否在范围内
if(
( ( (0 <= i+dj) && (i+dj < n) ) &&
( (0 <= j-di) && (j-di < n) ) ) &&
( ( (0 <= i+di+dj) && (i+di+dj < n) ) &&
( (0 <= j+dj-di) && (i+dj-di < n) ) )
){
// 检查第三个,第四个"顶点"是否是#
// 也就是检查这四个点能否构成正方形
if(
(cs[i+dj][j-di] == '#') &&
(cs[i+di+dj][j+dj-di] == '#')
){
// 如果这个正方形的边长 大于 已经找到的最大的正方形的边长
if( ((di*di) + (dj*dj)) > max_leng_pow ){
// 记录该正方形的四个顶点的位置,以及该正方形的边长
ans[0][0] = i;
ans[0][1] = j;
ans[1][0] = i + di;
ans[1][1] = j + dj;
ans[2][0] = i + dj;
ans[2][1] = j - di;
ans[3][0] = i + di + dj;
ans[3][1] = j + dj - di;
max_leng_pow = (di*di) + (dj*dj);
}
}
}
}
}
}
}
}
}
// 最后,按照给定的顺序依次输出四个顶点的坐标,记得+1
// A C B D
cout << ans[0][0]+1 << " " << ans[0][1]+1 << endl; // A
cout << ans[2][0]+1 << " " << ans[2][1]+1 << endl; // c
cout << ans[1][0]+1 << " " << ans[1][1]+1 << endl; // B
cout << ans[3][0]+1 << " " << ans[3][1]+1 << endl; // D
}
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
solve();
}
// 64 位输出请用 printf("%lld")