In 1704, French mathematician Sebastien Truchet proposed a tiling system that started with simple motifs and used its rotations and random placement to create quite interesting tiling patterns. In this problem we will calculate the area enclosed by the curves in a special case of his tiling system.
Motif 0 | Motif 1 |
Observe the two motifs here. Motif 0 is a square of length 2 units on each side. There are two circles with radius 1 unit drawn at two opposite corners of the square. Motif 1 is just a 90 degrees rotation of the first one (or you can think of it as drawing the circles on the other two corners).
Using just two basic motifs as shown here, we can tile an area to create rather interesting artistic patterns. They do not have to be symmetrically placed; we can lay out these motifs randomly to cover an area. If we then use a tool like paint bucket (found in most paint programs) at a particular point in the pattern, we can color a contiguous region with one color.
In this problem you'll be given a description of such a tiling pattern and then be asked how much area would it color if we use paint bucket starting at specific points.
Here is one illustration: We have the motifs randomly placed on a 9 x 9 grid. Then we used a blue color at position (2, 4) (here 2 denotes the distance from the top and 4 denotes the distance from left). It colored the entire contiguous region it found bounded by the grid's boundary and the curves themselves. We could achieve the same effect if we used the color at position (4, 6), (0, 6), (1, 7) etc. However, using the paint bucket on the perimeter of the curves (such as (3, 4)) will only color the perimeter line of the curves. They will not fill up a region with any color.
Input
Input starts with an integer T (≤ 100), denoting the number of test cases.
Each case starts with a line containing two integers R and C (1 ≤ R, C ≤ 100). Each of the next R lines contains the row description given in the binary form. The basic motifs are numbered 0 and 1. For example, the accompanying picture's first row can be described as 0001
.The next line contains an integer Q (1 ≤ Q ≤ 100) denoting the number of queries. Each query will be of the form x y (0 ≤ x ≤ 2R, 0 ≤ y ≤ 2C), where x and y are integers denoting the row and column number where the paint bucket tool will be used.
Output
For each case, print the case number in a single line. Then for each query, print one number giving the area enclosed by the boundary and the curves that contain that point. If the point in question itself lies on a curve, you can assume the enclosed area to be zero. Errors less than 10-6 will be ignored.
Sample
Sample Input | Sample Output |
---|---|
3 1 2 01 4 0 0 2 0 0 1 0 2 2 2 01 00 1 2 2 3 1 1 0 1 2 3 1 4 2 | Case 1: 0.7853981634 4.8584073464 0 4.8584073464 Case 2: 4.7853981634 Case 3: 7.2876110196 1.5707963268 |
Notes
This is a special judge problem; wrong output format may cause wrong answer
.