shunfurh 于 2017.08.27 00:24 提问

Box Pushing

Karatos needs to push a box through a straight alley. There are some unmovable barriers on the ground. The barriers and the box are all cuboids and their surfaces are parallel or perpendicular to the wall of the alley. Karatos is not allowed to rotate or turn over the box. He does not know whether it is possible to do that. Write a program to tell him the answer.

Since the heights of cuboids are trivial, we can draw the map on an ichnography. Karatos starts from the x-axis. The left wall of alley is just on the y-axis. All barriers are rectangles. No two of them overlap.

Input
The input consists of multiple test cases. Each test case begins with 2 positive integers: L, W which represents the length of the box's projection on x axis and y axis respectively. The second line consists of a positive integer which represents the width of the alley. The third line consists of a non-negative integer N (<=20) which is the number of barriers. The following N lines give out the description of barriers. Each line has 4 non-negative integers: x1, x2, y1, y2, which represents the left, right, front and back sides of the barrier.

Output
For each test case, output "Possible" or "Impossible" in a single line.

Sample Input:
1 1
5
2
1 2 3 4
3 4 1 2
2 2
5
2
1 2 3 4
3 4 1 2
Sample Output:
Possible
Impossible

1个回答

devmiao      2017.08.28 01:14