Định lý Pick

Định lý Pick: Cho một đa giác đơn giản có tất cả các đỉnh là điểm nguyên (điểm có tọa độ nguyên), định lý Pick mô tả mối quan hệ giữa diện tích \({\displaystyle A}\), số điểm nguyên nằm trong đa giác \({\displaystyle i}\) và số điểm nguyên nằm trên biên đa giác \({\displaystyle b}\) như sau: \({\displaystyle A=i+{\frac {b}{2}}-1}\).

Chứng minh chi tiết: Pick's theorem

Một số mở rộng của định lý Pick:

Nếu lấy diện tích của mỗi ô lưới là 1 đơn vị, trên lưới hình bình hành, định lý Pick vẫn đúng. Nếu áp dụng cho tam giác lưới bất kỳ, định lý Pick có dạng \({\displaystyle A=2 \times i+b-2}\).
Với đa giác không đơn giản \({\displaystyle P}\), định lý Pick có dạng \({\displaystyle A=i+{\frac {b}{2}}-\chi (P)}\), trong đó \({\displaystyle \chi (P)}\) là đặc trưng Euler của \({\displaystyle P}\).
Tổng quát lên không gian nhiều chiều: Đa thức Ehrhart.
Định lý Pick tương đương với công thức Euler (\({\displaystyle V-E+F=2}\)).

Ví dụ (POJ 1265)

Đề bài tóm tắt

Trên hệ tọa độ vuông góc, một robot xuất phát từ một điểm bất kỳ và thực hiện \(\textit{n}\) bước di chuyển, mỗi lần di chuyển sang phải \(\textit{dx}\), lên trên \(\textit{dy}\), cuối cùng tạo thành một đa giác đơn giản khép kín trên mặt phẳng. Hỏi có bao nhiêu điểm trên biên, bao nhiêu điểm trong đa giác, và diện tích đa giác là bao nhiêu.

Hướng giải

Bài này sử dụng ba kiến thức sau:

Với đoạn thẳng nối hai điểm nguyên, nếu cả \(\textit{dx}\) và \(\textit{dy}\) đều khác \(0\), số điểm nguyên mà đoạn thẳng đi qua là \(\gcd(\textit{dx}, \textit{dy}) + 1\). Nếu tính cho toàn bộ đa giác, các điểm trùng ở đầu cuối sẽ bị tính lặp, nên mỗi cạnh chỉ cần cộng \(\gcd(\textit{dx},\textit{dy})\). Ở đây, \(\textit{dx},\textit{dy}\) lần lượt là số bước theo trục hoành và trục tung. Nếu \(\textit{dx}\) hoặc \(\textit{dy}\) bằng \(0\), số điểm là giá trị tuyệt đối của phần khác \(0\).
Định lý Pick: Diện tích của đa giác đơn giản có đỉnh là điểm nguyên = số điểm trên biên / 2 + số điểm trong đa giác - 1.
Diện tích đa giác bất kỳ bằng nửa tổng giá trị tuyệt đối của tổng các tích chéo giữa các cặp điểm liên tiếp (có thể tính bằng công thức tích chéo hoặc tích phân theo chiều kim đồng hồ).

Mã mẫu tham khảo

#include <cmath>
#include <iomanip>
#include <iostream>
using namespace std;
constexpr 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() {
  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;
}

Last updated on this page:, Update history
Found an error? Want to help improve? Edit this page on GitHub!
Contributors to this page:OI-wiki
All content on this page is provided under the terms of the CC BY-SA 4.0 and SATA license, additional terms may apply