Constellation (Codeforces 32D)
Tags: Implement, implementation

A star map in Berland is a checked field n × m squares. In each square there is or there is not a star. The favourite constellation of all Berland's astronomers is the constellation of the Cross. This constellation can be formed by any 5 stars so, that for some integer x (radius of the constellation) the following is true:   the 2nd is on the same vertical line as the 1st, but x squares up  the 3rd is on the same vertical line as the 1st, but x squares down  the 4th is on the same horizontal line as the 1st, but x squares left  the 5th is on the same horizontal line as the 1st, but x squares right Such constellations can be very numerous, that's why they are numbered with integers from 1 on the following principle: when two constellations are compared, the one with a smaller radius gets a smaller index; if their radii are equal — the one, whose central star if higher than the central star of the other one; if their central stars are at the same level — the one, whose central star is to the left of the central star of the other one.Your task is to find the constellation with index k by the given Berland's star map.

Input: The first line contains three integers n, m and k (1 ≤ n, m ≤ 300, 1 ≤ k ≤ 3·107) — height and width of the map and index of the required constellation respectively. The upper-left corner has coordinates (1, 1), and the lower-right — (n, m). Then there follow n lines, m characters each — description of the map. j-th character in i-th line is «*», if there is a star in the corresponding square, and «.» if this square is empty.

Output: If the number of the constellations is less than k, output -1. Otherwise output 5 lines, two integers each — coordinates of the required constellation. Output the stars in the following order: central, upper, lower, left, right.


Sample Inputs:
5 6 1
....*.
...***
....*.
..*...
.***..

5 6 2
....*.
...***
....*.
..*...
.***..

7 7 2
...*...
.......
...*...
*.***.*
...*...
.......
...*...

Sample Outputs:
2 5
1 5
3 5
2 4
2 6

-1

4 4
1 4
7 4
4 1
4 7

Solution (Python):
import sys
input = sys.stdin.readline
(n, m, k) = map(int, input().split())
s = [list(input().rstrip()) for _ in range(n)]
c = 0
for k0 in range(1, min(n, m)):
    for i in range(k0, n - k0):
        l0 = min(i, n - i - 1)
        si = s[i]
        for j in range(k0, m - k0):
            if si[j] == '.':
                continue
            if si[j - k0] == si[j + k0] == '*':
                if s[i - k0][j] == s[i + k0][j] == '*':
                    c += 1
                    if c == k:
                        ans = [(i + 1, j + 1)]
                        ans.append((i + 1 - k0, j + 1))
                        ans.append((i + 1 + k0, j + 1))
                        ans.append((i + 1, j + 1 - k0))
                        ans.append((i + 1, j + 1 + k0))
                        for i in range(5):
                            ans[i] = ' '.join(map(str, ans[i]))
                        sys.stdout.write('\n'.join(ans))
                        exit()
print(-1)

Solution (Python):
(n, m, k) = map(int, input().split())
l = []
for i in range(n):
    l += [input()]
q = [0] * (n // 2 + 1)
for i in range(n):
    for j in range(m):
        if l[i][j] == '*':
            r = 1
            while r:
                if i + r < n and i - r > -1 and (j + r < m) and (j - r > -1):
                    if l[i + r][j] == '*' and l[i - r][j] == '*' and (l[i][j + r] == '*') and (l[i][j - r] == '*'):
                        q[r - 1] += 1
                else:
                    break
                r += 1
r = -1
for i in range(n // 2 + 1):
    if k > q[i]:
        k -= q[i]
    else:
        r = i
        break
if r == -1:
    print(-1)
else:
    r = i + 1
    q = []
    for i in range(n):
        for j in range(m):
            if l[i][j] == '*':
                if i + r < n and i - r > -1 and (j + r < m) and (j - r > -1):
                    if l[i + r][j] == '*' and l[i - r][j] == '*' and (l[i][j + r] == '*') and (l[i][j - r] == '*'):
                        q += [(i + 1, j + 1)]
    (x, y) = q[k - 1]
    print(x, y)
    print(x - r, y)
    print(x + r, y)
    print(x, y - r)
    print(x, y + r)

Solution (Python):
import sys
from array import array

def input():
    return sys.stdin.buffer.readline().decode('utf-8')
(n, m, k) = map(int, input().split())
a = [tuple(map(lambda c: c == '*', input().rstrip())) for _ in range(n)]
cnt = [0] * 400
for i in range(1, n - 1):
    for j in range(1, m - 1):
        if not a[i][j]:
            continue
        for (rad, ui, di, lj, rj) in zip(range(1, 400), range(i - 1, -1, -1), range(i + 1, n), range(j - 1, -1, -1), range(j + 1, m)):
            if a[ui][j] and a[di][j] and a[i][lj] and a[i][rj]:
                cnt[rad] += 1
rad = -1
for i in range(300):
    cnt[i + 1] += cnt[i]
    if cnt[i] >= k:
        rad = i
        k -= cnt[i - 1]
        break
else:
    print(-1)
    exit()
for i in range(rad, n - rad):
    for j in range(rad, m - rad):
        if a[i][j] and a[i - rad][j] and a[i + rad][j] and a[i][j - rad] and a[i][j + rad]:
            k -= 1
            if k == 0:
                print(f'{i + 1} {j + 1}\n{i - rad + 1} {j + 1}\n{i + rad + 1} {j + 1}\n{i + 1} {j - rad + 1}\n{i + 1} {j + rad + 1}')
                exit()