跳转至

Pick 定理

Pick 定理

Pick 定理：給定頂點均為整點的簡單多邊形，皮克定理説明了其面積 \({\displaystyle A}\) 和內部格點數目 \({\displaystyle i}\)、邊上格點數目 \({\displaystyle b}\) 的關係：\({\displaystyle A=i+{\frac {b}{2}}-1}\)。

具體證明：Pick's theorem

它有以下推廣：

  • 取格點的組成圖形的面積為一單位。在平行四邊形格點，皮克定理依然成立。套用於任意三角形格點，皮克定理則是 \({\displaystyle A=2 \times i+b-2}\)。
  • 對於非簡單的多邊形 \({\displaystyle P}\)，皮克定理 \({\displaystyle A=i+{\frac {b}{2}}-\chi (P)}\)，其中 \({\displaystyle \chi (P)}\) 表示 \({\displaystyle P}\) 的 歐拉特徵數。
  • 高維推廣：Ehrhart 多項式
  • 皮克定理和 歐拉公式（\({\displaystyle V-E+F=2}\)）等價。

一道例題 (POJ 1265)

題目大意

在直角座標系中，一個機器人從任意點出發進行 \(\textit{n}\) 次移動，每次向右移動 \(\textit{dx}\)，向上移動 \(\textit{dy}\)，最後會形成一個平面上的封閉簡單多邊形，求邊上的點的數量，多邊形內的點的數量，多邊形面積。

題解

這道題目其實用了以下三個知識：

  • 以整點為頂點的線段，如果邊 \(\textit{dx}\) 和 \(\textit{dy}\) 都不為 \(0\)，經過的格點數是 \(\gcd(\textit{dx}, \textit{dy}) + 1\)，當然，如果要算一整個圖形的，多加的點會被上一條邊計算，也就不需要加了。那麼一條邊覆蓋的點的個數為 \(\gcd(\textit{dx},\textit{dy})\)，其中，\(\textit{dx},\textit{dy}\) 分別為線段橫向佔的點數和縱向佔的點數。如果 \(\textit{dx}\) 或 \(\textit{dy}\) 為 \(0\)，則覆蓋的點數為 \(\textit{dy}\) 或 \(\textit{dx}\)。
  • Pick 定理：平面上以整點為頂點的簡單多邊形的面積 = 邊上的點數/2 + 內部的點數 - 1。
  • 任意一個多邊形的面積等於按順序求相鄰兩個點與原點組成的向量的叉積之和的一半（這個也可以通過順時針定積分求得）。
參考代碼 
 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
#include <cmath>
#include <cstdio>
#include <iostream>
using namespace std;
const int MAXN = 110;

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

int gcd(int x, int y) { return y == 0 ? x : gcd(y, x % y); }  // 求最大公约数

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

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