Description
Given the three vertices of a triangle with integer coordinates, return the number of lattice points strictly inside the triangle. Vertices form a non-degenerate triangle.
Examples
Input:
vertices = [[0,0],[4,0],[0,4]]Output:
3Explanation:
By Pick's theorem the triangle has interior lattice points (1,1), (2,1), and (1,2), counting 3.
Input:
vertices = [[0,0],[2,0],[0,2]]Output:
0Explanation:
The triangle with legs of length 2 contains no strictly interior lattice points, so the count is 0.
Input:
vertices = [[0,0],[5,0],[0,5]]Output:
6Explanation:
Pick's theorem yields 6 interior lattice points for the right triangle with vertices (0,0),(5,0),(0,5).
Constraints
- •
Triangle is non-degenerate - •
-10⁶ ≤ coords ≤ 10⁶