Integral Points Inside Triangle.cpp

#include <cmath>
#include <algorithm>

class Solution {
public:
    long long int InternalCount(long long int p[], long long int q[], long long int r[]) {
        // Calculate area using the shoelace formula
        long long int area2 = abs(p[0]*(q[1] - r[1]) + q[0]*(r[1] - p[1]) + r[0]*(p[1] - q[1]));

        // Function to calculate the gcd
        auto gcd = [](long long int a, long long int b) {
            while (b) {
                long long int t = b;
                b = a % b;
                a = t;
            }
            return a;
        };

        // Calculate the number of boundary points
        long long int b1 = gcd(abs(p[0] - q[0]), abs(p[1] - q[1]));
        long long int b2 = gcd(abs(q[0] - r[0]), abs(q[1] - r[1]));
        long long int b3 = gcd(abs(r[0] - p[0]), abs(r[1] - p[1]));
        long long int boundaryPoints = b1 + b2 + b3;

        // Applying Pick's theorem to find internal points
        long long int internalPoints = (area2 - boundaryPoints + 2) / 2;

        return internalPoints;
    }
};