⚙️AlgorithmIntermediate

Pick's Theorem

Key Points

  • •
    Pick's Theorem connects area and lattice-point counts for any simple polygon with integer-coordinate vertices.
  • •
    It states A = I + B/2 - 1, where A is area, I interior lattice points, and B boundary lattice points.
  • •
    You can compute A quickly with the Shoelace formula using integer arithmetic on twice the area to avoid floating-point error.
  • •
    The number of lattice points on each polygon edge equals gcd(|dx|,|dy|), so B is the sum of these gcds over all edges.
  • •
    Rearranged, I = A - B/2 + 1 and, using integers, 2I = A2 - B + 2 where A2 = 2A is twice the area.
  • •
    Use 64-bit integers for coordinates and accumulate area in 128-bit to prevent overflow in competitive programming.
  • •
    Pick's Theorem only applies to simple (non-self-intersecting) polygons whose vertices are lattice points.
  • •
    This is a powerful tool in CF 1600–2000 problems for counting interior points, scaling polygons, and mixing with number theory.

Prerequisites

  • →Greatest Common Divisor (Euclidean Algorithm) — Boundary counts per edge require computing gcd(|dx|,|dy|) efficiently and correctly.
  • →Shoelace Formula for Polygon Area — Pick’s Theorem needs the polygon area; the Shoelace formula provides an exact integer method.
  • →2D Cross Product and Orientation — Understanding signed area helps apply the Shoelace formula and reason about polygon orientation.
  • →Integer Arithmetic and Overflow Handling — Accurate results depend on using appropriate integer widths (e.g., __int128 accumulation).
  • →Basic Polygon Representation — Vertices must be processed in cyclic order, and edge deltas computed correctly.
  • →Simple vs. Self-Intersecting Polygons — Pick’s Theorem assumes simplicity; knowing the difference avoids invalid applications.

Detailed Explanation

Tap terms for definitions

01Overview

Pick's Theorem is a beautiful bridge between geometry and number theory for lattice polygons—polygons whose vertices all have integer coordinates. It states that the area of any simple (non-self-intersecting) lattice polygon can be computed using just the number of lattice points inside it and on its boundary: A = I + B/2 - 1. This turns area questions into counting problems and vice versa. In competitive programming, it’s especially useful because we can compute boundary lattice points via greatest common divisors (gcd) along each edge, and we can compute the polygon’s area robustly with the integer-only Shoelace formula. Together, they let us calculate any of A, B, or I from the other two using safe integer arithmetic. Why is this valuable? Many tasks ask for counts of grid points inside shapes, or they give you an area and ask about possible configurations of lattice points. With Pick’s Theorem plus two standard tools—Shoelace area and edge gcd—you can solve these in O(n) for an n-vertex polygon. It also behaves nicely under integer scaling: if you scale the polygon by an integer k, its area scales by k^2 and its boundary count by k, which makes interior-point counts predictable. While elegant, the theorem has strict conditions: it applies only to simple polygons with integer vertices. Handling degeneracies, self-intersections, and overflow requires care in implementation.

02Intuition & Analogies

Imagine walking along the edges of a polygon drawn on graph paper where the dots are integer-coordinate points. Two things are easy to see: 1) some dots lie on the boundary (you step on them while walking the edges), and 2) some dots lie strictly inside the shape. Pick’s Theorem says that the area inside the fence you’ve walked is determined exactly by how many dots you stepped on (boundary points) and how many dots are fenced inside (interior points). Think of the grid like Lego studs on a base plate. A straight segment connecting two studs advances in uniform steps from one stud to another. The number of studs touched by that segment is dictated by how many equal steps you can break the move into—this count is exactly gcd(|dx|,|dy|). For example, moving 6 to the right and 4 up can be done in steps of (3,2) repeated twice, so the edge touches gcd(6,4) = 2 studs on the boundary per unit step, plus structure at the junctions. Now consider area. Instead of measuring with a ruler, count tiny 1×1 squares under the polygon. There’s a deep but intuitive balance: every time you add a boundary stud, you add “half” a square on average to the area; every interior stud adds a whole square; and the formula subtracts 1 to fix the offset. Small examples make it tangible: a 1×1 square has I = 0, B = 4, and A = 1; the theorem gives 0 + 4/2 - 1 = 1. A 2×1 rectangle has I = 0, B = 6, A = 2; we get 0 + 3 - 1 = 2. This half-per-boundary-point intuition arises because along edges you “own” about half the squares, while interior points “own” one full square each. The theorem beautifully captures this balance.

03Formal Definition

Let P be a simple polygon in \(\), i.e., all vertex coordinates are integers and the polygon does not self-intersect. Denote by \(I\) the number of lattice points strictly inside P, and by \(B\) the number of lattice points on the boundary (including vertices and any lattice points along edges). Pick’s Theorem states: \[ + - 1. \] Equivalently, using twice the area \(A_2 = 2A\), we have a purely integer identity: \[ . \] For computational purposes, the area \(A\) of a polygon with vertices \((, )\) in order is computed by the Shoelace formula: \[ A = , \] where indices are cyclic (\(, , \)). The boundary lattice-point count is the sum over edges of the gcd of coordinate differences: \[ B = (, ). \] Each term counts lattice points contributed by an edge, and the sum equals the total number of distinct boundary lattice points. Once \(A\) and \(B\) are known, \(I\) follows from the rearrangement \(I = A - B/2 + 1\).

04When to Use

Use Pick’s Theorem whenever you are working with simple polygons whose vertices are on integer coordinates and you need any of: 1) the polygon’s area, but you prefer integer arithmetic; 2) the number of lattice points strictly inside the polygon; 3) relationships under integer scaling or decomposition. Typical CF problems include: counting interior grid points of a given lattice polygon; computing B or I for a triangle or convex polygon; deducing I after scaling coordinates by an integer k; and combining with number theory (e.g., parity or divisibility arguments using (A_2 = 2I + B - 2)). It’s also great when floating-point precision is risky: the Shoelace formula paired with 128-bit integer accumulation yields exact results for large coordinates. If the polygon is simple but concave, Pick’s Theorem still holds. When you only have edges or segments, gcd-based boundary counts solve subproblems like “How many lattice points lie on this segment?” Avoid it for non-simple (self-intersecting) polygons, polygons with non-integer vertices, or regions with holes (the classic theorem requires a small modification for holes). In such cases, either preprocess to obtain a simple polygon, use alternative area formulas, or apply generalizations (e.g., Pick’s theorem with holes: (A = I + B/2 - 1 + H), where H is the number of holes).

⚠️Common Mistakes

  • Using floating-point for area: The Shoelace sum can be very large, and doubles may introduce rounding errors. Always compute twice the area with integers (e.g., 128-bit accumulation) and divide by 2 at the end if needed.
  • Miscounting boundary points per edge: The number of lattice points on a closed segment from (x1,y1) to (x2,y2) is (\gcd(|\Delta x|, |\Delta y|) + 1). Summing this over edges double-counts vertices. The correct boundary total for the polygon is (\sum \gcd(|\Delta x|, |\Delta y|)) (no +1 per edge).
  • Forgetting simplicity: Pick’s Theorem assumes the polygon is simple. Applying it to a self-intersecting polygon can yield nonsense. Validate or ensure input polygons are simple or triangulate correctly.
  • Overflow: Cross products (x_i y_{i+1} - x_{i+1} y_i) can exceed 64-bit if coordinates are up to 1e9 and n is large. Accumulate in (__int128) in C++ to be safe.
  • Wrong vertex order or missing closure: Shoelace needs consistent cyclic order (clockwise or counterclockwise) and wrap-around from last to first point. Forgetting the wrap or mixing orders can flip the sign or give incorrect sums (always take absolute value at the end).
  • Degenerate edges and duplicates: Consecutive identical points or zero-length edges can skew gcd counting. Clean input or handle zero deltas carefully ((\gcd(a,0)=a)).

Key Formulas

Pick's Theorem

Explanation: Relates the area of a simple lattice polygon to its interior and boundary lattice points. Given any two of A, I, B, you can compute the third.

Shoelace (twice area)

Explanation: Twice the polygon area equals the absolute sum of signed 2D cross products of consecutive vertices. This keeps all computations in integers.

Boundary count via gcd

Explanation: The number of lattice points on the polygon boundary equals the sum, over edges, of gcd of coordinate differences. This avoids double-counting vertices.

Segment lattice points

Explanation: Counts lattice points on a closed segment including both endpoints. Useful as a building block; the +1 is not used when summing around a polygon.

Interior from area and boundary

Explanation: A rearrangement of Pick’s Theorem to solve for the number of interior lattice points once A and B are known.

Integer form of Pick's

Explanation: Equivalent to Pick’s Theorem but uses only integers. Useful to avoid fractions or when proving parity properties.

2D cross product

Explanation: Gives the signed area of the parallelogram spanned by two vectors. The Shoelace formula is a sum of such cross products.

Scaling by integer k

Explanation: If a lattice polygon is scaled by integer factor k, area scales by and boundary by k, letting you compute the new interior count I'.

GCD edge cases

Explanation: Edge-case rules ensure robust boundary counting when an edge is axis-aligned or degenerate.

Shoelace variant

Explanation: An equivalent form of the Shoelace formula using neighbors on both sides. It can be derived by rearranging the standard expression.

Complexity Analysis

All computations derived from Pick’s Theorem can be done in linear time with respect to the number of vertices n. Computing twice the area (A2) via the Shoelace formula requires a single pass summing n cross products, which is O(n). Computing the boundary count B requires another pass summing n gcd operations on consecutive vertex differences, also O(n). The total time complexity is therefore O(n). In competitive settings, gcd is constant-time with extremely small constants, so the approach is fast even for large n (e.g., up to 2e5 vertices). Space complexity is O(1) auxiliary beyond storing the input vertices. You only need a few accumulators for the Shoelace sum and boundary sum. If you process vertices online (streaming), you can keep space to O(1) plus the last vertex (though most problems provide the entire polygon, so you store O(n)). A crucial practical complexity point is integer width. Individual cross products * may reach about 1e18 when coordinates are ~1e9, and summing n of them can exceed 64-bit. To ensure correctness, accumulate the Shoelace sum in 128-bit (C++ __int128) and only convert to 64-bit if safe. GCD inputs remain within 64-bit (differences of coordinates), so std::gcd with 64-bit integers is fine. Overall, the algorithm is both time- and memory-efficient, suitable for CF 1600–2000 constraints.

Code Examples

Compute area (A), boundary points (B), and interior points (I) of a lattice polygon
1#include <bits/stdc++.h>
2using namespace std;
3
4// Use long long for coordinates; accumulate area in __int128 to avoid overflow.
5struct Pt { long long x, y; };
6
7// Returns non-negative twice the area (A2 = 2A) using the Shoelace formula.
8long long twice_area(const vector<Pt>& p) {
9    int n = (int)p.size();
10    __int128 s = 0; // extended accumulator
11    for (int i = 0; i < n; ++i) {
12        int j = (i + 1) % n;
13        s += (__int128)p[i].x * p[j].y - (__int128)p[j].x * p[i].y;
14    }
15    if (s < 0) s = -s; // absolute value for area
16    // Convert back to 64-bit; caller must ensure it fits if needed.
17    return (long long)s;
18}
19
20// Counts boundary lattice points B via sum of gcd(|dx|, |dy|) over edges.
21long long boundary_points(const vector<Pt>& p) {
22    int n = (int)p.size();
23    long long B = 0;
24    for (int i = 0; i < n; ++i) {
25        int j = (i + 1) % n;
26        long long dx = llabs(p[j].x - p[i].x);
27        long long dy = llabs(p[j].y - p[i].y);
28        B += std::gcd(dx, dy); // gcd(a,0)=a; works for axis-aligned edges
29    }
30    return B;
31}
32
33int main() {
34    ios::sync_with_stdio(false);
35    cin.tie(nullptr);
36
37    int n;
38    if (!(cin >> n)) return 0;
39    vector<Pt> p(n);
40    for (int i = 0; i < n; ++i) cin >> p[i].x >> p[i].y;
41
42    long long A2 = twice_area(p);          // 2A (integer)
43    long long B = boundary_points(p);      // boundary lattice points
44
45    // From A2 = 2I + B - 2 => 2I = A2 - B + 2
46    long long twoI = A2 - B + 2;
47    // I must be an integer for lattice polygons; assert non-negative even value
48    // but avoid runtime assertions in production; here we trust input is valid.
49    long long I = twoI / 2;
50
51    // Output A as a rational if needed. Many problems want A2, B, I.
52    cout << "A2 " << A2 << "\n"; // twice the area
53    cout << "B  " << B  << "\n"; // boundary lattice points
54    cout << "I  " << I  << "\n"; // interior lattice points
55
56    return 0;
57}
58

Reads a simple lattice polygon, computes twice the area with the Shoelace formula using 128-bit accumulation, counts boundary points via gcd on each edge, and derives interior points from Pick’s Theorem in the integer form 2I = A2 − B + 2. This avoids floating-point errors and runs in linear time.

Time: O(n)Space: O(1) extra (O(n) to store input)
Triangle case: count interior and boundary lattice points for a lattice triangle
1#include <bits/stdc++.h>
2using namespace std;
3
4struct Pt { long long x, y; };
5
6long long twice_area_triangle(const Pt& a, const Pt& b, const Pt& c) {
7    __int128 s = 0;
8    s += (__int128)a.x * b.y - (__int128)b.x * a.y;
9    s += (__int128)b.x * c.y - (__int128)c.x * b.y;
10    s += (__int128)c.x * a.y - (__int128)a.x * c.y;
11    if (s < 0) s = -s;
12    return (long long)s;
13}
14
15long long boundary_points_triangle(const Pt& a, const Pt& b, const Pt& c) {
16    auto edgeB = [](const Pt& u, const Pt& v) {
17        long long dx = llabs(v.x - u.x);
18        long long dy = llabs(v.y - u.y);
19        return std::gcd(dx, dy);
20    };
21    return edgeB(a,b) + edgeB(b,c) + edgeB(c,a);
22}
23
24int main(){
25    ios::sync_with_stdio(false);
26    cin.tie(nullptr);
27
28    Pt a,b,c; cin >> a.x >> a.y >> b.x >> b.y >> c.x >> c.y;
29
30    long long A2 = twice_area_triangle(a,b,c);
31    long long B  = boundary_points_triangle(a,b,c);
32    long long I  = (A2 - B + 2) / 2; // from 2I = A2 - B + 2
33
34    cout << "A2 " << A2 << "\n";
35    cout << "B  " << B  << "\n";
36    cout << "I  " << I  << "\n";
37
38    return 0;
39}
40

Specialized for triangles, this program uses three-point formulas for A2 and B, then applies Pick’s Theorem to compute I. Triangles are common in geometry subproblems and make for quick correctness checks.

Time: O(1)Space: O(1)
Scaling a lattice polygon by integer k: compute new I' and B' without recomputing geometry
1#include <bits/stdc++.h>
2using namespace std;
3
4struct Pt { long long x, y; };
5
6long long twice_area(const vector<Pt>& p) {
7    int n = (int)p.size();
8    __int128 s = 0;
9    for (int i = 0; i < n; ++i) {
10        int j = (i + 1) % n;
11        s += (__int128)p[i].x * p[j].y - (__int128)p[j].x * p[i].y;
12    }
13    if (s < 0) s = -s;
14    return (long long)s;
15}
16
17long long boundary_points(const vector<Pt>& p) {
18    int n = (int)p.size();
19    long long B = 0;
20    for (int i = 0; i < n; ++i) {
21        int j = (i + 1) % n;
22        long long dx = llabs(p[j].x - p[i].x);
23        long long dy = llabs(p[j].y - p[i].y);
24        B += std::gcd(dx, dy);
25    }
26    return B;
27}
28
29int main(){
30    ios::sync_with_stdio(false);
31    cin.tie(nullptr);
32
33    int n; long long k; 
34    cin >> n >> k; // integer scaling factor k
35    vector<Pt> p(n);
36    for (int i = 0; i < n; ++i) cin >> p[i].x >> p[i].y;
37
38    long long A2 = twice_area(p); // 2A
39    long long B  = boundary_points(p);
40
41    // After scaling by integer k: A' = k^2 * A, so A2' = k^2 * A2; B' = k * B.
42    // Then from 2I' = A2' - B' + 2 we get interior points of the scaled polygon.
43    __int128 A2p = (__int128)k * k * A2;
44    __int128 Bp  = (__int128)k * B;
45    __int128 twoIp = A2p - Bp + 2; // integer-safe
46    long long Ip = (long long)(twoIp / 2);
47
48    cout << "B' " << (long long)Bp << "\n";
49    cout << "I' " << Ip << "\n";
50
51    return 0;
52}
53

Demonstrates how Pick’s Theorem behaves under integer scaling. Instead of reconstructing the scaled polygon and recomputing gcds and cross products, we scale area and boundary counts analytically and then obtain the new interior count I'.

Time: O(n) to get initial A2 and BSpace: O(1) extra (O(n) to store input)