Skip to content

Pick's Theorem

Pick's Theorem

Pick's Theorem: Given a simple polygon whose vertices are all integer lattice points, Pick's theorem relates its area \({\displaystyle A}\) to the number of interior lattice points \({\displaystyle i}\) and the number of boundary lattice points \({\displaystyle b}\): \({\displaystyle A=i+{\frac {b}{2}}-1}\).

For a detailed proof, see: Pick's theorem

It has the following generalizations:

  • Take the area of the unit cell formed by the lattice points as one unit. Pick's theorem still holds for parallelogram lattices. Applied to any triangular lattice, Pick's theorem becomes \({\displaystyle A=2 \times i+b-2}\).
  • For a non-simple polygon \({\displaystyle P}\), Pick's theorem is \({\displaystyle A=i+{\frac {b}{2}}-\chi (P)}\), where \({\displaystyle \chi (P)}\) denotes the Euler characteristic of \({\displaystyle P}\).
  • Higher-dimensional generalization: Ehrhart polynomial.
  • Pick's theorem is equivalent to Euler's formula (\({\displaystyle V-E+F=2}\)).

Example Problem (POJ 1265)

Problem Description

In a Cartesian coordinate system, a robot starts from an arbitrary point and makes \(\textit{n}\) moves. In each move, it moves \(\textit{dx}\) units to the right and \(\textit{dy}\) units upward. This forms a closed simple polygon on the plane. Find the number of lattice points on its boundary, the number of lattice points in its interior, and its area.

Solution

This problem utilizes the following three concepts:

  • For a line segment with integer lattice endpoints, if neither \(\textit{dx}\) nor \(\textit{dy}\) is \(0\), the number of lattice points it passes through is \(\gcd(\textit{dx}, \textit{dy}) + 1\). However, when considering the entire polygon, points counted multiple times by adjacent edges should not be double-counted. Thus, the number of lattice points covered by a single edge is \(\gcd(\textit{dx},\textit{dy})\), where \(\textit{dx}\) and \(\textit{dy}\) are the horizontal and vertical spans of the segment, respectively. If \(\textit{dx}\) or \(\textit{dy}\) is \(0\), the number of covered points is \(\textit{dy}\) or \(\textit{dx}\).
  • Pick's Theorem: The area of a simple polygon with integer lattice vertices = (number of boundary points)/2 + (number of interior points) - 1.
  • The area of any polygon equals half the sum of the cross products of vectors formed by consecutive vertices with the origin (this can also be derived via clockwise definite integration).
Reference Code 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include <cmath>
#include <iomanip>
#include <iostream>
using namespace std;
constexpr int MAXN = 110;

struct node {
  int x, y;
} p[MAXN];

// Calculate the greatest common divisor
int gcd(int x, int y) { return y == 0 ? x : gcd(y, x % y); }

// Calculate area
int area(int a, int b) { return p[a].x * p[b].y - p[a].y * p[b].x; }

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  int t, ncase = 1;
  cin >> t;
  while (t--) {
    int n, dx, dy, x, y, num = 0, sum = 0;
    cin >> n;
    p[0].x = 0, p[0].y = 0;
    for (int i = 1; i <= n; i++) {
      cin >> x >> y;
      p[i].x = x + p[i - 1].x, p[i].y = y + p[i - 1].y;
      dx = x, dy = y;
      if (x < 0) dx = -x;
      if (y < 0) dy = -y;
      num += gcd(dx, dy);
      sum += area(i - 1, i);
    }
    if (sum < 0) sum = -sum;
    cout << fixed << setprecision(1);
    cout << "Scenario #" << ncase++ << ":\n";
    cout << ((sum - num + 2) >> 1) << ' ' << num << ' ' << sum * 0.5 << "\n\n";
  }
  return 0;
}
本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用