Tiling Polygons

In a polygon tiling game you fill the inside of a polygon using only a given set of basic shapes called tiles. That is, you cut the whole polygon into pieces so that every piece has exactly the shape of one of the given tiles. This problem uses a simple form of the game. Two kinds of rectangular tiles are available, shown in Figure 7. Their width and height are $1 \times 3$ and $3 \times 1$. Use these two tiles to fill a rectilinear polygon, a polygon whose edges are all vertical or horizontal. Figure 8(a) shows such a polygon, and Figure 8(b) fills it with three $3 \times 1$ tiles and one $1 \times 3$ tile.

Figure 7: the $1 \times 3$ tile and the $3 \times 1$ tile

The coordinate system follows these rules.

1. The polygon is placed so that its lowest edge lies on the x-axis and its leftmost edge lies on the y-axis, as in Figure 8.
2. The polygon is given as an ordered list of points that names all of its vertices. The list starts at the lower left vertex, the leftmost vertex lying on the x-axis, and runs counterclockwise. The polygon in Figure 8(a) is the sequence [A, B, C, D, E, F, G, H].
3. A grid, a square whose width and height are both one, is written as a pair $(x, y)$, where $x$ and $y$ are the coordinates of its top right vertex. Figure 8(a) prints the coordinates of every grid inside that grid.
4. A tile is written as a triple $(x, y, z)$. Here $x$ and $y$ are the coordinates of the middle one of the three grids the tile covers, and $z$ is the orientation. A horizontal tile has $z = 0$ and a vertical tile has $z = 1$. Figure 9 shows two examples.

Write a program that finds a way to fill a given polygon. The polygon can always be filled.

Figure 8: an example of a tiling

Figure 9: two examples of the $(x, y, z)$ notation

The input holds several test cases.

Each case describes one polygon to fill. The first line holds a single integer $N$ ($4 \le N < 100$), the number of vertices of the polygon. Each of the next $N$ lines holds one vertex in the order described above, its x-coordinate and its y-coordinate separated by a single space.

The area of a polygon is always less than 1000, and every coordinate is an integer less than 100.

A line holding a single zero ends the input. Do not process that line.

For each case print the list of tiles that fills the polygon. Print one tile per line as x y z, three numbers separated by a single space.

Several tilings can exist, so print only the one this rule picks. Scan the grids of the polygon by increasing $y$, and for equal $y$ by increasing $x$. Let $g$ be the first grid that no tile covers yet. Only two tiles can cover $g$: the horizontal tile whose leftmost grid is $g$, and the vertical tile whose bottom grid is $g$. Place the horizontal tile first, and if that choice cannot fill the whole polygon, place the vertical tile instead. Repeat until no grid is left. This rule fixes exactly one tiling.

Sort the tiles you print by increasing $y$, and for equal $y$ by increasing $x$. Two different tiles never share a middle grid, so this order is unique.

Print a blank line between cases.