

Pick 定理

Pick 定理¶

Pick 定理：给定顶点坐标均是整点（或正方形格子点）的简单多边形，皮克定理说明了其面积和内部格点数目、边上格点数目的关系：。

具体证明： Pick's theorem

它有以下推广：

取格点的组成图形的面积为一单位。在平行四边形格点，皮克定理依然成立。套用于任意三角形格点，皮克定理则是。
对于非简单的多边形，皮克定理，其中表示的 欧拉特征数 。
高维推广：Ehrhart 多项式
皮克定理和 欧拉公式 （）等价。

一道例题 (POJ 1265)¶

题目大意¶

给一个平面上的简单多边形，求边上的点，多边形内的点，多边形面积。

Solution¶

这道题目其实用了以下三个知识：

以格子点为顶点的线段，覆盖的点的个数为，其中，分别为线段横向占的点数和纵向占的点数。如果或为，则覆盖的点数为或。
Pick 定理：平面上以格子点为顶点的简单多边形的面积 = 边上的点数/2 + 内部的点数 + 1。
任意一个多边形的面积等于按顺序求相邻两个点与原点组成的向量的叉积之和（这个也可以通过顺时针定积分求得）。于是这题就愉快地做完了

#include <cmath>
#include <cstdio>
#include <iostream>
using namespace std;
const int MAXN = 110;
struct node {
  int x, y;
} p[MAXN];
inline int gcd(int x, int y) { return y == 0 ? x : gcd(y, x % y); }
inline 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 协议之条款下提供，附加条款亦可能应用

Pick 定理

Pick 定理¶

一道例题 (POJ 1265)¶

题目大意¶

Solution¶

评论