Triangle Encapsulation
TimeLimit:2000MS MemoryLimit:65536KB
64-bit integer IO format:%lld
未提交 | 登录后收藏
Problem Description
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.
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.
Input
Output
SampleInput
4 4 2 -1 -2 2 2 4 4 -3 0 -1
SampleOutput
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 XFigure 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.