COCI '14 Contest 5 #5 Jabuke

Points: 15 (partial)

Time limit: 1.0s

Memory limit: 128M

Problem type

It is often heard that the apple doesn't fall far from the tree. But is that really so?

The National Statistics Department has tracked the falling of apples in a fruit garden for $G$ $G$ consecutive years. The fruit garden can be represented as a matrix with dimensions $R \cdot S$ $R \cdot S$ . Each field of the matrix can contain more than one apple tree.

Interestingly enough, each year there was exactly one apple fall, so the Department decided to write down $G$ $G$ pairs of numbers $(r_i, s_i)$ $(r_{i}, s_{i})$ that denote the row and column of the location where the apple fell during the $i^{th}$ $i^{t h}$ year. Moreover, by next year, a new tree grew at that location.

Your task is to determine the squared distance between the nearest tree and the apple that fell, measured in unit fields of the matrix (we assume it is that tree from which the apple fell).

The distance between fields $(r_1, s_1)$ $(r_{1}, s_{1})$ and $(r_2, s_2)$ $(r_{2}, s_{2})$ in the matrix are calculated as:

$\displaystyle d((r_1, s_1),(r_2, s_2)) = \sqrt{(r_1 - r_2)^2 + (s_1 - s_2)^2}$ $d ((r_{1}, s_{1}), (r_{2}, s_{2})) = \sqrt{(r_{1} - r_{2})^{2} + (s_{1} - s_{2})^{2}}$

Input

The first line of input contains two integers, $R$ $R$ and $S$ $S$ $(1 \le R, S \le 500)$ $(1 \leq R, S \leq 500)$ , the number of rows and columns of the matrix.

Each of the following $R$ $R$ lines contains $S$ $S$ characters x or .. The character . denotes an empty field, and the character x denotes a field with at least one tree.

The fruit garden will initially contain at least one tree.

After that, an integer $G$ $G$ $(1 \le G \le 10^5)$ $(1 \leq G \leq 10^{5})$ follows, the number of years the fruit garden has been under observation.

Each of the following $G$ $G$ lines describes the falls of the apples. Each line contains a pair of integers $(r_i, s_i)$ $(r_{i}, s_{i})$ that denote the row and column of the location where the apple fell in the $i^{th}$ $i^{t h}$ year.

Output

Output $G$ $G$ numbers, the required squared distances from the task, each in its own line.

Scoring

In test cases worth 30% of total points, it will hold $G \le 500$ $G \leq 500$ .

Sample Input 1

Copy

3 3
x..
...
...
3
1 3
1 1
3 2

Sample Output 1

Copy

4
0
5

Explanation for Sample Output 1

The closest apple to the one that fell in the first year is the apple in the field $(1,1)$ $(1, 1)$ . The apple that fell in the second year fell on the exact field where the tree is located, so the squared distance is $0$ $0$ . The apple that fell in the third year is equally distant to all three existing trees in the fruit garden.

Sample Input 2

Copy

5 5
..x..
....x
.....
.....
.....
4
3 1
5 3
4 5
3 5

Sample Output 2

Copy

Comments

0

XIAOAGE commented on Dec. 28, 2015, 3:06 a.m. ← edited →

I think there's a little typo on the definition of the distance:

$d((r_1, s_1),(r_2, s_2))$ $d ((r_{1}, s_{1}), (r_{2}, s_{2}))$

It should be without square root according to the problem statement.

0

cheesecake commented on Dec. 28, 2015, 3:18 a.m.

The formula given is for distance, you're to output the square of that, similar to this problem.