Flipping Colors
Time limit1sMemory limit128 MB
Repeatedly split each rectangle in fixed ratios h:v and flip the colors of the upper-right and lower-left parts; report the color reached by each query point.
- Level
Medium5 of 10
- Topics
- Recursion, Divide and conquer, Math, Implementation
- Solved
- No attempts yet
Problem
A rectangle whose sides are parallel to the - and -axes, with its lower-left corner at , is being painted. You may think of the rectangle as a display of almost infinite resolution; initially the whole rectangle is black. Two real numbers and are given, and then the following process is applied.
- Draw a vertical line that splits the horizontal sides of the rectangle in the ratio measured from the left.
- Draw a horizontal line that splits the vertical sides of the rectangle in the ratio measured from the bottom.
- These two lines divide the rectangle into four smaller rectangles.
- The upper-left and the lower-right sub-rectangles keep their color unchanged.
- The other two sub-rectangles (upper-right and lower-left) have their color flipped (black to white or white to black), and each of them is then subjected to exactly the same process that was just applied to the bigger rectangle.
- This process continues (in principle) forever.
Given a point inside the original rectangle that never lies on the boundary of any rectangle appearing during the painting process, determine the color of the point.
Input
The input consists of several test cases. The first line of each case contains four real numbers: the width and the height of the rectangle, followed by the ratios and (with ). Thus the rectangle occupies the region . The next line contains one integer , the number of points to consider. Each of the following lines contains two numbers, the - and -coordinates of a point. The input ends with a line whose four values are all (0 0 0 0), which must not be processed.
Output
For each test case, first print a line of the form Case k:, where is the case number starting from . Then, for each input point, print the color of that point (black or white) on its own line.