Triangle Encapsulation

Time Limit: 1 Second    Memory Limit: 32768 KB

In this problem you have to find integer points in a triangle.

Input

Each line of the input to your program will specify the x- and y-coordinates of the three vertices of a triangle in the xy -plane, starting at some vertex and proceeding clockwise. For each vertex, the x-coordinate will be specified before the y-coordinate. Each x- and y-coordinate will be an integer in the range (-9, 9). The input file will consist of one or more lines.
Each triangle specified in the input will encapsulate at least one point with integer coordinates.

Within each line of input, the difference between the largest and smallest x-coordinate will not exceed 9.

Output

For each triangle specified in the input, the output will list all points in the xy-plane which have integer coordinates and lie in the triangle's interior. (Such points are said to be encapsulated by the triangle.) Points that lie on one of the triangle's borders (in particular, the vertices of the triangle) will not be listed in the output.

Figure 1 illustrates the first triangle of the below example, and the points with integer coordinates in its interior. Note that (1,3) lies on this triangle's border and is therefore not encapsulated by the triangle.

Points (x, y) which are listed on one line of output have the same y-coordinate; the x-coordinates of these points are in increasing order from left to right.

The y-coordinates of points in the interior of a triangle will be in decreasing order from one line of output to the next line.

Each (x,y) point will be printed in a nine-column output field. Points that have the same x-coordinate (and pertain to the same triangle) will be listed in the same nine-column output field. Here is a formatting template between two lines of the above output:

                           ( 2,  3) ( 3,  3)
12345678901234567890123456789012345678901234567890
(-1,  2) ( 0,  2) ( 1,  2) ( 2,  2) ( 3,  2)

Each nine-column output field has the following layout (unless it is blank):

Column 1: opening parenthesis

Columns 2-3 : x coordinate (right justified)

Column 4: comma

Columns 5-7 : y -coordinate (right justified)

Column 8 : closing parenthesis.

Column 9: blank space to separate current nine-column field from the next one, if there is a next one.

The line(s) containing the smallest x-value pertaining to a particular triangle (such as -1 for the first triangle in the above example) will not start with a blank output field.

There will not be a blank output field between two non-blank ones on a given line.

After listing the points encapsulated by each triangle, your program will produce one blank line of output. There will not be any additional blank lines in the output.

Sample Input

4  4  2 -1 -2  2
2  4  4 -3  0 -1

Sample Output

Program 4 by team X
                           ( 2,  3) ( 3,  3)
(-1,  2) ( 0,  2) ( 1,  2) ( 2,  2) ( 3,  2)
         ( 0,  1) ( 1,  1) ( 2,  1)
                  ( 1,  0) ( 2,  0)

         ( 2,  3)
         ( 2,  2)
( 1,  1) ( 2,  1)
( 1,  0) ( 2,  0) ( 3,  0)
( 1, -1) ( 2, -1) ( 3, -1)
                  ( 3, -2)

End of program 4 by team X

Submit

Source: Rocky Mountain 2000