题解 | 最大正方形

def solve(testcase):
    n = II()
    s = [I() for _ in range(n)]

    A = []

    for i in range(n):
        for j in range(n):
            if s[i][j] == '#':
                A.append((i, j))

    m = len(A)

    M = 0
    res = []

    for i in range(m):
        x1, y1 = A[i]
        for j in range(i + 1, m):
            x2, y2 = A[j]

            dx, dy = x2 - x1, y2 - y1

            x3, y3 = x1 + dy, y1 - dx

            if 0 <= x3 < n and 0 <= y3 < n and s[x3][y3] == '#':

                x4, y4 = x3 + dx, y3 + dy

                if 0 <= x4 < n and 0 <= y4 < n and s[x4][y4] == '#':

                    LEN = dx ** 2 + dy ** 2

                    if M < LEN:
                        M = LEN
                        res = [(x1 + 1, y1 + 1), (x2 + 1, y2 + 1), (x3 + 1, y3 + 1), (x4 + 1, y4 + 1)]

    for x, y in res:
        print(x, y)

for testcase in range(1):
    solve(testcase)