

Pick 定理

Pick's theorem¶

Pick's theorem: Given a simple polygon whose vertices are all integral points, Pick’s theorem proves the relationship between its area $A$ , the number of internal points $i$ , and the number of points on the edge $b$ : $A=i+{\frac {b}{2}}-1$ .

Detailed proof: Pick's theorem

It has the following generalizations:

The area of the graph composed of grid points is one unit. Pick's theorem still stands for parallelogram grid. For any triangle lattice, Pick's theorem is $A=2 \times i+b-2$ .
For non-simple polygons $P$ , Pick’s theorem $A=i+{\frac {b}{2}}-\chi (P)$ , where ${\displaystyle \chi ( P))$ represents the Euler characteristic of $(\displaystyle P)$ .
Higher-dimensional: Ehrhart polynomials.
Pick's theorem is equivalent to Euler's formula ( $V-E+F=2$ ).

Sample problem (POJ 1265)¶

Topic¶

Given a simple polygon on a plane, find the points on the side, inside the polygon, and the area of the polygon.

Solution¶

This topic includes the following three key points:

The number of points covered by the line segment with integral points as the vertex is $\gcd(\textit{dx},\textit{dy})$ , where $\textit{dx} and \textit{dy}$ are the number of points covered by line horizontally and vertically, respectively. If $\textit{dx}$ or $\textit{dy}$ is $0$ , the number of points covered is $\textit{dy}$ or $\textit{dx}$ .
Pick theorem: The area of a simple polygon with integral points as its vertices on the plane = the number of points on the side / 2 + the number of internal points + 1.
The area of any polygon is equal to the sum of the cross product of the vector composed of two adjacent points and the origin in order (this can also be obtained by clockwise definite integral).

So this question is finished easily.

#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's theorem¶

Sample problem (POJ 1265)¶

Topic¶

Solution¶

评论