Pick's Theorem and Lattice Geometry

A lattice polygon has integer-coordinate vertices. Pick’s theorem relates its area to counts of lattice points inside and on the boundary, turning a potentially enormous point enumeration into one edge scan. The program combines exact doubled shoelace area with GCD boundary counts to obtain the number of strictly interior lattice points. The assumptions—simple polygon, no holes and positive area—are part of the theorem, not optional implementation details.

Prerequisites: Shoelace Formula; Greatest Common Divisor; simple polygons.

Build the idea

1. State the theorem and variables

   Let A be ordinary area, I the number of lattice points strictly inside and B the number on the polygon boundary. Pick’s theorem says A=I+B/2−1. Rearranging with exact doubled area A2 gives I=(A2−B+2)/2. A polygon need not be convex; a simple concave lattice boundary satisfies the same formula.

2. Count lattice steps on an edge

   For endpoints differing by (dx,dy), let g=gcd(|dx|,|dy|). Dividing the displacement by g gives a primitive integer step with coprime components. The lattice points on the closed edge are its start plus k primitive steps for k=0…g, so there are g+1. Along a polygon boundary count each edge half-open, contributing g, to avoid counting vertices twice.

   $$2I=2A-B+2$$

3. Connect to an area argument

   One way to understand Pick is to triangulate lattice polygons into primitive lattice triangles of area one half. Add the relation across pieces: shared internal edges cancel the boundary corrections, leaving a single −1 for a simple connected polygon without holes. This explains both why lattice coordinates matter and why holes change the constant term rather than obeying the same formula unchanged.

4. Trace a rectangle

   For (0,0),(4,0),(4,3),(0,3), area is 12 and doubled area 24. Edge GCDs are 4,3,4,3, summing to B=14. Therefore I=(24−14+2)/2=6, namely x=1,2,3 with y=1,2. No scan over all 20 boundary-and-interior grid positions is needed.

5. Implement exact arithmetic and assumptions

   Use long long for coordinate products, accumulated doubled area and boundary count; take absolute area only after summing signed edge terms. std::gcd from <numeric> handles vertical and horizontal edges naturally. Under n≤100000 and |coordinate|≤10^6, the absolute cross-sum bound is 2·10^17. A zero-length edge contributes gcd(0,0)=0, but input still promises a valid simple positive-area polygon.

This is a complete program. Compile with C++17 and enter the input described below.

#include<iostream>
#include<vector>
#include<numeric>
#include<cstdlib>
struct Point{
    long long x,y;
};
int main(){
    int n;
    std::cin>>n;
    std::vector<Point>p(n);
    for(auto&a:p){
        std::cin>>a.x>>a.y;
    }
    long long signedTwice=0,boundary=0;
    for(int i=0;i<n;++i){
        Point a=p[i],b=p[(i+1)%n];
        signedTwice+=a.x*b.y-a.y*b.x;
        boundary+=std::gcd(std::llabs(b.x-a.x),std::llabs(b.y-a.y));
    }
    long long twice=std::llabs(signedTwice);
    // Simple, positive-area lattice polygon is an input promise.
    long long interior=(twice-boundary+2)/2;
    std::cout<<twice<<' '<<boundary<<' '<<interior<<'\n';
}

Complexity analysis

O(n log(C+1)) time for n Euclidean GCD calculations, where C bounds absolute edge-coordinate differences (≤2·10^6 here); area work is O(n). O(n) stored vertices and O(1) additional accumulators. No dependence on the polygon’s bounding-box area.

Example input and output

Read n (3..100000), then a simple positive-area polygon without holes, with integer coordinates within ±10^6 in boundary order. Print absolute doubled area, boundary lattice count and strictly interior lattice count.

Input

4
0 0
4 0
4 3
0 3

Output

24 14 6

Area 12 and boundary count 14 give six strictly interior lattice points by Pick’s theorem.

Practical applications

Use for counting interior lattice positions and checking area/count identities in integer polygon problems. Shoelace alone gives area; GCD adds boundary counts; Pick connects them. If the question asks for points under an open curve or on a non-lattice polygon, a different counting method is needed.

Check your understanding

Why does one polygon edge contribute gcd(|dx|,|dy|), not gcd+1, to the total boundary count?

Put it into practice

Check a lattice triangle, a concave lattice polygon and the reversed rectangle.