|시간 제한||메모리 제한||제출||정답||맞은 사람||정답 비율|
|5 초||512 MB||0||0||0||0.000%|
In a polygon tiling game, you are required to fill a polygon with a set of basic shapes called tiles. This is equivalent to cutting up the entire polygon into a number of small pieces; each piece must have exactly the same shape as one of the provided tiles. Let us consider a simple version of the game. Two types of rectangular tiles are given as shown in Figure 7. Their width/height are 1/3 and 3/1 respectively. You are asked to use these two types of tiles to tile a rectilinear polygon (that is, a polygon with only vertical or horizontal edges). For instance, Figure 8(a) shows such a polygon and Figure 8(b) shows how it can be properly tiled with three 3 × 1 tiles and one 1 × 3 tile.
Figure 7: 1 × 3 tile and 3 × 1 tile
The coordinate system used in this game is described by the following rules:
Your task is to write a program that finds a way to tile a given polygon. The polygon is known to be tillable. If there is more than one ways of tiling, you are only required to find one of them.
Figure 8: An example of tiling
Figure 9: An example of tiling
Input consists of multiple test cases.
Each case describes a polygon to be tiled. The first line contains a single integer N (4 ≤ N < 100) that denotes the number of vertices of the polygon. The subsequent N lines specify the vertices of the polygon in the order stated above; one line per vertex. A vertex is specified as its x-coordinate followed by its y-coordinate, separated by a white space.
You may assume the area of a polygon is always less than 1000, as well as each coordinate value is an integer less than 100.
A line that contains a single zero indicates the end of input, and this line should not be processed.
The sample input below denotes the polygon shown in Figure 8(a).
For each case, the output produces a list of tiles that fills the polygon specified in the input file. A tile is specified as a triple x y z as described above, separated by a white space; one tile per line. The tiles may appear in any order.
Print a blank line between cases.
The sample output below represents the solution shown in Figure 8(b).
8 1 0 4 0 4 4 3 4 3 3 0 3 0 1 1 1 0
2 3 0 2 2 0 3 1 0 4 3 1