Ուղարկել | Բոլոր լուծումները | Լավագույն լուծումները | Վերադառնալ ցուցակին |
ACM_0125 - INTERIOR LATTICE POINTS |
A lattice point is a point whose coordinates on a rectangular coordinate system are integers. An interior lattice point is a lattice point that is inside a given polygon and not on its boundary. For example, the drawing below shows a triangle having six interior lattice points.
Write a program that reads an input containing three pairs of coordinates (xA, yA), (xB, yB), (xC, yC), where each coordinate is an unsigned integer with a value less than or equal to 100. The numbers in the line are separated exactly by one space and are in the order xA yA xB yB xC yC. The coordinates describe three distinct (but possibly collinear) lattice points. If the given coordinates describe a triangle with non-zero area, then the program should display on the screen the number of interior lattice points of the triangle. Otherwise, the program should display on the screen the number zero. (If the three points are collinear, then there are no interior lattice points.)
Input
The input starts with an integer N (0 ≤ N ≤ 255). This is followed by N input cases. Each input case is a list of six unsigned integers with values not exceeding 100. The six integers xA yA xB yB xC yC correspond to the coordinates (xA, yA), (xB, yB), (xC, yC).
Output
For every input case, print the number of interior lattice points in one line.
Examples
№ |
stdin |
stdout |
1 |
4 0 0 100 0 100 100 0 0 98 100 100 100 0 0 99 100 100 100 0 0 99 99 100 100 |
4851 49 0 0 |
Ավելացրեց. | Հրանտ Հովհաննիսյան |
Ամսաթիվ. | 2014-02-06 |
Ժամանակի սահմանափակումը. | 1s |
Ծրագրի տեքստի սահմանափակումը. | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Լեզուներ. | Բոլորը բացի ASM32 ASM64 GAWK CLPS CLOJURE D ERL FSHARP FORTRAN GOSU HASK ICON ICK NEM NIM OBJC-CLANG PICO PIKE PYPY PYPY3 PY_NBC RUST SCM guile CHICKEN SED TCL WHITESPACE |
Աղբյուրը. | Philippines Multi-Provincial 2013.I |