Integral Points Inside Triangle

JavaView on GFG

Time: O(1)

Space: O(1)

Intuition

Count lattice points (integer coordinates) strictly inside a triangle. Pick theorem: I = A - B/2 + 1.

Algorithm

1A = area via shoelace formula (use abs and integer arithmetic).
2B = boundary points on each edge = gcd(|dx|,|dy|). I = A - B/2 + 1.

Common Pitfalls

•Pick theorem: Interior = Area - Boundary/2 + 1. Area must be computed as integer (multiply by 2 to avoid fractions).

Integral Points Inside Triangle.java

Java

// Approach: Pick's theorem: I = A - B/2 + 1 where A = triangle area (shoelace), B = boundary lattice points.
// Time: O(1) Space: O(1)
class Solution {
    long InternalCount(long p[], long q[], long r[]) {
        long x1 = p[0], y1 = p[1];
        long x2 = q[0], y2 = q[1];
        long x3 = r[0], y3 = r[1];
        
        long points = getEdgePoint(x1, y1, x2, y2) 
                    + getEdgePoint(x2, y2, x3, y3) 
                    + getEdgePoint(x3, y3, x1, y1) + 3;
                    
        long area = Math.abs(x1 * (y2 - y3) + x2 * (y3 - y1) + x3 * (y1 - y2));
        
        return (area - points + 2) / 2;
    }
    
    long gcd(long a, long b) 
    {
        if(b == 0)
            return a;
            
        return gcd(b, a % b);
    }
    
    long getEdgePoint(long x1, long y1, long x2, long y2)
    {
        if(x1 == x2)
            return Math.abs(y2 - y1) - 1;
            
        if(y1 == y2)
            return Math.abs(x2 - x1) - 1;
            
        return gcd(Math.abs(x2 - x1), Math.abs(y2 - y1)) - 1;
    }
};

Was this solution helpful?