HDU 1705 Count the Grid 完整解析

給定三角形三頂點整數座標，求三角形內部（不含邊界）整數格點個數。經典應用皮克定理。

皮克定理

對於頂點為整數座標的簡單多邊形：

S = A + B/2 - 1

• S：多邊形面積
• A：內部格點數（所求）
• B：邊界格點數（含頂點）

推導：A = S - B/2 + 1

邊界格點數計算：最大公約數法

線段 (x1,y1) 到 (x2,y2) 上的整數點數（含端點）為：

gcd(|x1-x2|, |y1-y2|) + 1

三條邊界點數總和 B = gcd(dx1,dy1) + gcd(dx2,dy2) + gcd(dx3,dy3)（三頂點各算一次，剛好抵銷重複的 +1）。

面積計算：向量外積

三角形面積 S = |(x1-x0)(y2-y0) - (y1-y0)(x2-x0)| / 2。皮克定理中用 2S 為整數，避免浮點誤差。

完整 AC 程式碼

#include <bits/stdc++.h>
using namespace std;

struct Point { long long x, y; };

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

long long area2(Point a, Point b, Point c) {
    // 兩倍有向面積，取絕對值
    return llabs((b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x));
}

int main() {
    Point p[3];
    while (cin >> p[0].x >> p[0].y >> p[1].x >> p[1].y >> p[2].x >> p[2].y) {
        if (!p[0].x && !p[0].y && !p[1].x && !p[1].y && !p[2].x && !p[2].y) break;
        
        long long S2 = area2(p[0], p[1], p[2]); // 2 * 面積
        long long B = gcd(llabs(p[0].x - p[1].x), llabs(p[0].y - p[1].y))
                    + gcd(llabs(p[1].x - p[2].x), llabs(p[1].y - p[2].y))
                    + gcd(llabs(p[0].x - p[2].x), llabs(p[0].y - p[2].y));
        
        long long A = (S2 - B + 2) / 2; // 皮克定理：A = S - B/2 + 1 = (2S - B + 2)/2
        cout << A << endl;
    }
    return 0;
}

計蒜客 35 變體

僅給兩點 (x1,y1), (x2,y2)，第三點固定為原點 (0,0)。修改輸入讀取即可：

// 計蒜客 35 讀取方式
while (cin >> p[1].x >> p[1].y >> p[2].x >> p[2].y) {
    p[0] = {0, 0};
    // 其餘邏輯相同
}

關鍵點總結

• 座標範圍：題目未明確給出，建議用 long long 防溢位
• 退化三角形：三點共線時面積為 0，公式自動得出 A=0
• 輸入結束：六個 0 結束
• 精度：純整數運算，零誤差