Pick's theorem

Pick's theorem

Pick's theorem states that for a simple polygon whose vertices are all lattice points, the area ${\displaystyle A}$, the number of lattice points in its interior ${\displaystyle i}$, and the number of lattice points on its boundary ${\displaystyle b}$ satisfy ${\displaystyle A=i+{\frac {b}{2}}-1}$.

For a detailed proof, see Pick's theorem.

It has the following generalizations:

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

An example (POJ 1265)

Problem statement

In the Cartesian coordinate system, a robot starts from an arbitrary point and makes $\textit{n}$ moves. Each move is $\textit{dx}$ units to the right and $\textit{dy}$ units upward. The moves eventually form a closed simple polygon in the plane. Find the numbers of lattice points on and inside the polygon, and its area.

Solution

This problem uses the following three facts:

• For a segment whose endpoints are lattice points, if both $\textit{dx}$ and $\textit{dy}$ are nonzero, the number of lattice points it passes through is $0$. When counting an entire polygon, the duplicated endpoint is counted by the preceding edge and need not be added again. Thus an edge contributes $\gcd(\textit{dx}, \textit{dy}) + 1$ points, where $\gcd(\textit{dx},\textit{dy})$ and $\textit{dx},\textit{dy}$ are the numbers of lattice steps in the horizontal and vertical directions. If either $\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 lattice-point vertices is the number of boundary points divided by undefined, plus the number of interior points, minus undefined.
• The area of any polygon equals half the sum of the cross products of the vectors formed by each pair of consecutive points and the origin (this can also be derived using a line integral).

#include <cmath>
#include <iomanip>
#include <iostream>
using namespace std;
constexpr int MAXN = 110;

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

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

// Compute the signed area contribution
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;
}