Triangle Encapsulation

Time Limit: 2 Seconds
Memory Limit: 65536 KB

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 �C9..9. The input file will consist of one or more lines.

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.

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.

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

Figure 1 illustrates the first triangle of the above 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.

Source:

**Rocky Mountain 2000**
Submit
Status