Panchita is established with a Tacos Shop in the desert of North Mexico. To attract clients, she installed lots of signs like the one represented in Figure 1 all over the desert. The signs are intended to point in the direction of the shop; however, Panchita’s magnetic needle has a problem and only gives four directions: North, South, East and West. Thus, the signs only point to the shop with a certain approximation. In the desert, besides Panchita’s shop and the signs, there is nothing more. Panchita is happy with her signs: people transversing the desert usually make a deviation from their original route to follow the signs up to the shop, and she makes money. Her life would be perfect if there were no windstorms in the desert. The problem is that the wind makes the signs rotate, as if they were weather- cocks. After each storm, Panchita has to visit all the signs to fix their direction. Simulating Panchita’s Set-Up Figura 1: Panchita’s signs We may simulate a simplification of Panchita’s environment using a grid-based representation as the one in Figure 2. In this simulation, Panchita’s shop is represented by a single dark position and signs by two neighbour dark positions. Figura 2: Panchita’s grid world Directions are defined as angles, taking the East direction as the 0o reference (e.g., North is 90o, North-West is 135o).
2/4 A sign rotates around one of its dark positions: we call it the sign’s pivot position. This one corresponds to the side of the sign with an arrow shape (in Figure 1, the left side). That’s why pivot positions are represented in Figure 2 with triangles. Thus, a pivot position remains fixed in the map when a sign changes direction. The position that moves is called movable (see Figure 3). Figura 3: Signs rotate around pivot positions This representation obviously lacks lot of detail. Sign direction, for instance, can only be represented in multiples of 45o. Therefore, we will assume that wind may only leave signs pointing in directions which are multiples of 45o. Given a partial map of the desert after a windstorm, simulate the result of changing the signs’ directions to North, South, East or West, so that all them point approximately to Tacos Panchita. Figure 4 illustrates a hypothetical scenario. Figura 4: Signs after a windstorm The intended result is represented in Figure 2: a new map with the signs’ directions changed by moving movable positions.
3/4 To determine a corrected sign direction, you must first compute the direction α from Tacos Panchita to the sign’s pivot position. β, the new direction from the pivot to the respective movable position, will be the closest multiple of 90o, i.e., β will be the multiple of 90o such that α ∈ [β − 45o, β + 45o[ (note the closed left interval). Figure 5 illustrates this calculation: signs with pivots in area A must point to West, those with pivots in area B must point to South, and so on. Figura 5: New direction depends on the pivot position The following assumptions will be taken: • when correcting a sign’s direction, only the movable position may be changed • after a windstorm, there are no two objects “touching” each other • in the given partial map, every sign occupies exactly two positions; after correcting the signs’ directions, this may not be true, as the movable part of the sign may be out of the map and will not be represented Input The input will contain several test cases, each of them as described below. Consecutive test cases are separated by a single blank line. The input file consists of a variable number of lines as follows: First line: x y w h Next h lines: n p1 p2 ...pn where each pi is the x coordinate of a pivot position in the current line. Lines are presented in descending order of their y coordinates. In each line, pivot coordinates are presented in ascending order. Movable positions are not included in the input as they are not needed to solve the problem. Output For each test case, the output must follow the description below. The outputs of two consecutive cases will be separated by a blank line. Output should represent the map with the signs in the correct directions, and consist of a variable number of lines as follows: First line: x y w h where x and y are the (always positive) coordinates of Tacos Panchita’s position, and w and h are the width and the height of the given map Next h lines: m x1 x2 . . . xm
4/4 where each xj is the x coordinate of a movable position in the current line. Lines are presented in descending order of their y coordinates. In each line, movable coordinates are presented in ascending order. Pivot positions are not included in the output as they are kept unchanged. Sample Input 3376 16 12 0 16 12 15 Sample Output 3376 12 0 0 17 11 16