Hexagonal Sticks#5702
In this problem, we consider an infinite hexagonal grid. The grid consists of equal regular hexagonal cells arranged as shown below. The figure also illustrates the coordinate system used to identify each cell. Each cell of the grid can be empty or blocked.
Figure: A portion of the grid
A few sticks are placed randomly on this grid. The length of each stick is one "hexagonal unit," meaning the endpoints of a stick lie at the centers of neighboring cells. Your task is to move the sticks so that a closed regular hexagonal figure is formed.
The diagrams below show examples of closed hexagonal shapes made of sticks.
You are given the initial coordinates of the sticks placed on the grid. The coordinates of blocked cells are also provided. On each move, you may perform one of the following actions:
Select one stick and remove it.
Select one stick and rotate it by degrees (clockwise or counterclockwise) about one of its endpoints.
Select one stick and push it along its length by one hexagonal unit.
Sticks may never occupy a blocked cell. However, two sticks may occupy the same cells at the same time.
Consider the scenario shown above. There is an obstacle at coordinate and a stick from to . Four possible moves for the stick are illustrated.
After all moves are performed, you must ensure that a closed regular hexagonal shape is formed, with no other sticks lying around. This means the grid must contain exactly 6 \times x sticks, where is a positive integer. Can you achieve this in the minimum number of moves?
The first line contains an integer (T < 50), the number of test cases.
Each test case begins with a non-negative integer (S < 9) — the number of sticks available. Each of the next lines describes a stick in the format x_1\ y_1\ x_2\ y_2, indicating a stick from (x_1, y_1) to (x_2, y_2). All coordinates are valid and the length of each stick is one hexagonal unit.
The next line contains a non-negative integer (B < 20) — the number of obstacles. Each of the following lines contains the coordinates of an obstacle in the format x_1\ y_1. It is guaranteed that obstacles do not overlap with any stick. All coordinates (both sticks and obstacles) are integers in the range .
Note: The grid is infinite. In the optimal result, sticks forming a hexagon may lie outside the range .
For each test case, print the case number, followed by the minimum number of moves required. If it is impossible to form a hexagonal shape from the sticks, output impossible. Follow the sample input/output format exactly.
Example 1