折線分割平面：最大區域數計算與 C 語言實現

折線分割平面：最大區域數計算與 C 語言實現

經典的「直線分割平面」問題廣為人知，本文探討其變體——n 條折線分割平面的最大區域數。折線由兩條射線組成，頂點相連，形如「V」字形。例如：

• 1 條折線 → 2 個區域
• 2 條折線 → 最多 7 個區域（見下圖）

規律推導與通項公式

觀察數列：n=1 → 2、n=2 → 7、n=3 → 16、n=4 → 29... 一階差分為 5、9、13...（等差數列，公差 4），二階差分恆為 4。故為二次多項式：

f(n) = 2n² - n + 1

驗證：f(1)=2、f(2)=8-2+1=7、f(3)=18-3+1=16、f(4)=32-4+1=29 ✓

輸入輸出格式

• Input：首行整數 C（測試用例數），隨後 C 行，每行一整數 n (0 < n ≤ 10000)
• Output：每行輸出對應的最大分割數

C 語言參考實現

#include <stdio.h>

int main() {
    int T, n;
    long long ans;
    scanf("%d", &T);
    while (T--) {
        scanf("%d", &n);
        ans = 2LL * n * n - n + 1;  // 使用 long long 防止溢出
        printf("%lld\n", ans);
    }
    return 0;
}

關鍵點提示

• n 最大 10000，2n² 約 2×10⁸，32 位有符號整數（上限 2.1×10⁹）勉強容納，但建議用 long long 避免中間運算溢出
• 時間複雜度 O(C)，極快
• 純數學題，無需模擬幾何構造