Integral Points Inside Triangle

Given three non-collinear points whose co-ordinates are p(p1, p2), q(q1, q2) and r(r1, r2) in the X-Y plane. Return the number of integral / lattice points strictly inside the triangle formed by these points.
Note: A point in the X-Y plane is said to be an integral / lattice point if both its coordinates are integral.

Examples

Input: p = (0,0), q = (0,5), r = (5,0)
Output: 6
Explanation: 

As shown in figure, points (1,1) (1,2) (1,3) (2,1) (2,2) and (3,1) are the integral points inside the triangle. So total 6 are there.

Input: p = (62,-3), q = (5,-45), r = (-19,-23)
Output: 1129
Explanation: There are 1129 integral points in the triangle formed by p, q and r.

Expected Time Complexity: O(Log₂10⁹)
Expected Auxillary Space: O(1)

Constraints:
-10⁹ ≤ x-coordinate, y-coordinate ≤ 10⁹

Approach 01:

• C++

• Python

#include <iostream>
#include <cmath>
#include <algorithm>  // For std::min and std::max
using namespace std;

class Solution {
public:
    long long calculate_area(long long p[], long long q[], long long r[]) {
        // Using the Shoelace formula for the area of a triangle
        return abs(p[0] * (q[1] - r[1]) + q[0] * (r[1] - p[1]) + r[0] * (p[1] - q[1]));
    }

    long long boundary_lattice_points(long long p1[], long long p2[]) {
        // Using the custom gcd function to find the number of lattice points on the boundary line segment
        return custom_gcd(abs(p2[0] - p1[0]), abs(p2[1] - p1[1]));
    }

    long long InternalCount(long long p[], long long q[], long long r[]) {
        // Calculate the area of the triangle
        long long area = calculate_area(p, q, r);
        
        // Calculate the number of boundary lattice points
        long long b_points = boundary_lattice_points(p, q) + 
                             boundary_lattice_points(q, r) + 
                             boundary_lattice_points(r, p);
        
        // Calculate the number of interior lattice points using Pick's theorem
        // Interior points = (Area - Boundary points + 2) / 2
        long long interior_points = (area - b_points + 2) / 2;
        
        return interior_points;
    }

private:
    long long custom_gcd(long long a, long long b) {
        // Euclidean algorithm to find the greatest common divisor
        while (b != 0) {
            long long temp = b;
            b = a % b;
            a = temp;
        }
        return a;
    }
};

from math import gcd

class Solution:
    def calculate_area(self, p, q, r):
        # Using the Shoelace formula for the area of a triangle
        return abs(p[0]*(q[1] - r[1]) + q[0]*(r[1] - p[1]) + r[0]*(p[1] - q[1]))

    def boundary_lattice_points(self, p1, p2):
        # Using the gcd to find the number of lattice points on the boundary line segment
        return gcd(abs(p2[0] - p1[0]), abs(p2[1] - p1[1]))

    def InternalCount(self, p, q, r):
        # Calculate the area of the triangle
        area = self.calculate_area(p, q, r)
        
        # Calculate the number of boundary lattice points
        b_points = (self.boundary_lattice_points(p, q) + 
                    self.boundary_lattice_points(q, r) + 
                    self.boundary_lattice_points(r, p))
        
        # Calculate the number of interior lattice points using Pick's theorem
        # Interior points = Area - Boundary points / 2 + 1
        # Since the area is twice the actual area in the Shoelace formula, adjust accordingly
        interior_points = (area - b_points + 2) // 2
        
        return int(interior_points)