Interior Lattice Points#6247
A lattice point is a point in the Cartesian coordinate system whose coordinates are integers. An interior lattice point is a lattice point that lies strictly inside a given polygon and not on its boundary. For example, the figure below shows a triangle having six interior lattice points.
Given three pairs of coordinates (x_A, y_A), (x_B, y_B), (x_C, y_C), where each coordinate is an unsigned integer not exceeding , determine the number of interior lattice points inside the triangle formed by these points. If the points are collinear or do not form a valid triangle (i.e., have zero area), the result is (since there are no interior lattice points).
The input begins with an integer (0 \le n \le 255), the number of test cases. Each of the following lines contains six unsigned integers, not exceeding : x_A\ y_A\ x_B\ y_B\ x_C\ y_C. These correspond to the coordinates of the points (x_A, y_A), (x_B, y_B), (x_C, y_C).
For each test case, output a single integer on a separate line — the number of interior lattice points of the corresponding triangle.
Пример 1