32D.md (2431B)
1 Source: https://codeforces.com/problemset/problem/32/D 2 3 D. Constellation 4 5 time limit per test 6 7 2 seconds 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 stdin 16 17 output 18 19 stdout 20 21 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: 22 23 * the 2nd is on the same vertical line as the 1st, but *x* squares up 24 * the 3rd is on the same vertical line as the 1st, but *x* squares down 25 * the 4th is on the same horizontal line as the 1st, but *x* squares left 26 * the 5th is on the same horizontal line as the 1st, but *x* squares right 27 28 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. 29 30 Your task is to find the constellation with index *k* by the given Berland's star map. 31 32 Input 33 34 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. 35 36 Output 37 38 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. 39 40 Examples 41 42 Input 43 44 ``` 45 5 6 1 46 ....*. 47 ...*** 48 ....*. 49 ..*... 50 .***.. 51 ``` 52 53 Output 54 55 ``` 56 2 5 57 1 5 58 3 5 59 2 4 60 2 6 61 ``` 62 63 Input 64 65 ``` 66 5 6 2 67 ....*. 68 ...*** 69 ....*. 70 ..*... 71 .***.. 72 ``` 73 74 Output 75 76 ``` 77 -1 78 ``` 79 80 Input 81 82 ``` 83 7 7 2 84 ...*... 85 ....... 86 ...*... 87 *.***.* 88 ...*... 89 ....... 90 ...*... 91 ``` 92 93 Output 94 95 ``` 96 4 4 97 1 4 98 7 4 99 4 1 100 4 7 101 ```