Pick 定理與格點三角形內點計算：從數學原理到 ACM 題解

一、Pick 定理：幾何與數論的奇妙連結

Pick 定理 揭示了格點多邊形面積與內部/邊界格點數的精確關係：

S = N + L/2 - 1

• S：多邊形面積
• N：內部格點數
• L：邊界格點數（含頂點）

這一定理將連續幾何問題轉化為離散計數問題，是解決格點幾何題目的利器。

二、關鍵子問題：如何計算邊界格點數 L？

給定兩個格點 A(x₀,y₀)、B(x₁,y₁)，線段 AB 上的格點數等於 gcd(|x₁-x₀|, |y₁-y₀|)。

數學原理：線段參數方程 x = x₀ + λ(x₁-x₀), y = y₀ + λ(y₁-y₀)，λ ∈ [0,1]。要使 x,y 同時為整數，λ 的分母必須是 Δx、Δy 的公約數，故格點數 = gcd(Δx, Δy) + 1（含端點）。三角形三邊疊加時頂點被重複計算，總邊界點數 L = Σ gcd(Δxᵢ, Δyᵢ)。

代碼實現

int gcd(int a, int b) {
    return b == 0 ? a : gcd(b, a % b);
}

int OnEdge(int n, POINT *p) {
    int ret = 0;
    for (int i = 0; i < n; i++) {
        int dx = abs(p[i].x - p[(i+1)%n].x);
        int dy = abs(p[i].y - p[(i+1)%n].y);
        ret += gcd(dx, dy);
    }
    return ret;
}

三、三角形面積計算：叉積法

三角形面積的 2 倍 = 向量叉積絕對值：

int Int_area(POINT a, POINT b, POINT c) {
    return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
}

四、ACM 題目完整解法：三角形內部格點計數

問題：給定三角形三頂點（均為格點），求嚴格內部的格點數（不含邊界）。

推導：由 Pick 定理 S = N + L/2 - 1 得 N = S - L/2 + 1。因程序中 area = 2S，故 N = (area - L + 2) / 2。

完整 AC 代碼

#include <cmath>
#include <iostream>
#include <algorithm>
using namespace std;

typedef struct Point { int x, y; } POINT;

int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }

int Int_area(POINT a, POINT b, POINT c) {
    return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
}

int edgenum(POINT a, POINT b) {
    int dx = abs(a.x - b.x), dy = abs(a.y - b.y);
    return gcd(dx, dy);
}

int main() {
    POINT a, b, c;
    while (cin >> a.x >> a.y >> b.x >> b.y >> c.x >> c.y) {
        if (!a.x && !a.y && !b.x && !b.y && !c.x && !c.y) break;
        
        int area = abs(Int_area(a, b, c));      // 2倍面積
        int OnEdge = edgenum(a,b) + edgenum(b,c) + edgenum(c,a);
        int InSide = (area - OnEdge + 2) / 2;   // Pick定理反推內部點數
        
        cout << InSide << endl;
    }
    return 0;
}

五、測試樣例驗證

六、總結與拓展

• Pick 定理將幾何面積問題轉化為整數計數，避免了浮點精度問題
• gcd 計算邊界點數是核心技巧，體現了數論在計算幾何中的應用
• 此方法擴展至任意簡單多邊形同樣適用，只需累加各邊 gcd
• 注意：多邊形頂點需按順序（順/逆時針）給出，否則叉積面積會出現負值