POJ 3907 Build Your Home：多邊形面積計算（叉積公式）

題目大意

給定多邊形頂點座標（按順序），求其面積。多測試案例，每案例先給 n，再給 n 個點 (x, y)。n=0 結束。輸出面積四捨五入到整數。

解法：鞋帶公式（叉積求多邊形面積）

面積 = ½ |Σ (xᵢ·yᵢ₊₁ - xᵢ₊₁·yᵢ)|，其中 (xₙ₊₁, yₙ₊₁) = (x₁, y₁)。

代碼

#include 
#include 
using namespace std;

int main() {
    int n;
    while (cin >> n, n) {
        double x0, y0, x1, y1;
        cin >> x0 >> y0;
        double firstX = x0, firstY = y0;
        double sum = 0;
        for (int i = 1; i < n; ++i) {
            cin >> x1 >> y1;
            sum += x0 * y1 - x1 * y0;
            x0 = x1; y0 = y1;
        }
        // 閉合最後一條邊
        sum += x0 * firstY - firstX * y0;
        double area = fabs(sum) / 2.0;
        // 四捨五入到整數
        printf("%.0f\n", area + 1e-6);
    }
    return 0;
}

關鍵點

• 頂點順序已給定（順時針或逆時針），直接套公式。
• 雙精度累加，最後 `fabs` 取絕對值除 2。
• 輸出四捨五入：`printf("%.0f", area + 1e-6)` 防止浮點誤差導致 .5 向錯誤方向捨入。

複雜度

• 時間：O(n) 每案例。
• 空間：O(1)。

總結

POJ 3907 是多邊形面積計算的模板題。鞋帶公式（叉積和）是計算簡單多邊形面積的標準方法，代碼極短，只需注意閉合最後一條邊與浮點輸出格式。