Pick’s Theorem 学习笔记
Published:
Pick’s Theorem 学习笔记
题意：顺时针或逆时针地给出一个 $n$ 个顶点（顶点都是整点）的简单多边形，求这个多边形内部的整点数量（位于多边形形上的整点不算）。
Pick’s Theorem
对于一个顶点都是整点的简单多边形：
令 $I$ 为多边形内部的整点数量，$B$ 为多边形形上的整点数量，$A$ 为多边形面积。有公式：
\[A = I + \dfrac B 2 - 1\]比较有用的是它的变形：
\[I = A - \dfrac B 2 + 1\]Pick’s Theorem 的证明
对于一个 $B = 3$ 的三角形，其面积 $A$ 必然为 $\dfrac 1 2$。
采用数学归纳法的思路：将多边形剖成若干个 $B=3$ 的三角形，每次切除一个三角形，要么减少一个边上的点，要么将一个内部的点转化为边上的点，直到把多边形切成一个只有两点的线段。
因此 $A = \dfrac 1 2 (2I + B - 2) = I + \dfrac B 2 - 1$。
关于 Pick’s Theorem
皮克定理有许多有趣的应用，可以看 Matrix67 的这篇文章。
相关练习：P2735 [USACO3.4] 网 Electric Fences
此题解法
利用向量叉积求出多边形面积 $A$，用一点简单数论求出 $B$，再用 Pick’s Theorem 即可求出 $I$。
#include <bits/stdc++.h>
#define gcd __gcd
using namespace std;
typedef long long ll;
const int MAXN = 1000 + 5;
struct Point {
ll x, y;
Point(ll x, ll y) : x(x), y(y) {}
};
ll cross(Point &a, Point &b) {
return a.x * b.y - a.y * b.x;
}
int n;
vector<Point> points;
int main() { ios::sync_with_stdio(0); cin.tie(0);
while (1) {
cin >> n;
if (n == 0)
break;
for (int i = 1; i <= n; i++) {
int x, y; cin >> x >> y;
points.emplace_back(x, y);
}
points.push_back(points[0]);
ll area = 0, edge = 0;
for (int i = 1; i <= n; i++) {
auto &a = points[i-1], &b = points[i];
ll dx = abs(b.x - a.x), dy = abs(b.y - a.y);
area += cross(a, b);
edge += gcd(dx, dy);
}
area = abs(area) / 2;
cout << area - edge / 2 + 1 << '\n';
points.clear();
}
return 0;
}