Locksmith#3576
Mooks A, C, and M have been charged with creating locks for the Riddler's lair. They need to design locks comprised of flat interlocking pieces that can be unlocked only by separating these pieces while sliding them around on the surface of the doors. Unfortunately, while the mooks have come up with quite a few designs, they are not very good at determining which designs can actually be unlocked.
The pieces of the lock are axis-aligned polygons (that is, the sides are all either horizontal or vertical) in the plane. The lock can be manipulated by sliding any one polygon at a time in any direction, so long as doing so does not cause the polygon to overlap with any other polygon. Rotating a polygon is not allowed. A polygon is considered separable from the rest of the lock if there exists a sequence of moves (possibly involving several polygons) leading to a configuration such that it is possible to draw a straight line between the polygon and the remainder of the lock. Given a proposed lock configuration, your job is to determine the number of separable polygons.
The input file will contain multiple test cases. Each test case begins with a line with a single integer denoting the number of pieces in the lock. This line is followed by lines of space-separated integers each with the following format:
x_1 y_1 ... x_c y_c
Here, denotes the number of vertices in the piece, and x_i and y_i give the locations of the vertices in clockwise order. The sides of each piece are all either horizontal or vertical, and they alternate between the two. The pieces are guaranteed to have no overlapping area. Each test case has either or pieces, and for each test case, these pieces have a total of at most vertices. All coordinates given are integers between and inclusive. Input will be terminated by a case with pieces, which should not be processed.
For each input test case, print the number of separable pieces in the lock.
Example 1