Interior Points of Lattice Polygons#2447
A lattice point is a point with integer coordinates. A lattice polygon is a polygon with all vertices as lattice points.
The lattice points on the boundary of the polygon are boundary points (open dots in the figure above), and the points inside and not on the boundary of the polygon are interior points (filled dots in the figure above).
A polygon is convex if any line segment between two points of the polygon is inside (or on the boundary of) the polygon. Equivalently, the interior angle at each polygon vertex is less than degrees. Note that any segment between two points inside (and not on the boundary of) the polygon is entirely inside (and not on the boundary of) the polygon.
The interior points of a convex lattice polygon on any horizontal line form a single segment from the leftmost point to the rightmost point (which may be the same). Note that there may be no interior points (A), only one (B), or isolated interior points (C), as shown in the figures below.
Write a program that reads the vertices of a convex lattice polygon in standard order and outputs its interior points as a list of horizontal line segments. The vertices of a lattice polygon are in standard order if:
[(a)] The first vertex is the one with the largest value. If two vertices have the same value, the one with the smaller value is first.
[(b)] Vertices are given in clockwise order around the polygon.
The first line of input contains a single integer (1 \leq P \leq 1000), which is the number of data sets that follow. The first line of each data set contains the data set number, followed by a space, followed by the number of vertices (3 \leq N \leq 50) of the polygon. The remaining lines in the data set list the vertices, one per line in standard order. Each line contains the integer coordinate, a space, and the integer coordinate. All coordinates are integers.
For each data set, output several lines. The first line contains the data set number, a space, and the number of horizontal lines that contain interior points (this may be zero () or more). The lines of interior points, if any, follow one per line in order of decreasing value. Each line contains the coordinate, the coordinate of the leftmost point on that line, and the coordinate of the rightmost point on the same line, separated by spaces.
Example 1