HDU 折線分割平面：推導遞推公式 O(1) 計算最大分割數

問題描述

n 條折線（每條折線由兩條射線組成，形成一個「V」形）分割平面，求最大分割區域數。
n ≤ 10,000，多測試用例。

規律探索與公式推導

設 f(n) 為 n 條折線最大分割數。
n=1：1 條折線分 2 區 → f(1)=2
n=2：第 2 條折線可與第 1 條產生 4 個交點（每射線與對方兩射線各交一次），新增 5 區 → f(2)=7
n=3：第 3 條折線 4 射線，每射線與前 2 條折線的 4 條射線各交一次，共 8 交點，新增 9 區 → f(3)=16

觀察新增數：5, 9, 13, ... 等差數列，公差 4。
通項：第 k 條折線新增 4(k-1) + 1 = 4k - 3 區。
遞推：f(n) = f(n-1) + 4n - 3，f(1)=2。

求和：

f(n) = 2 + Σ_{k=2..n} (4k - 3)
     = 2 + 4 Σk - 3(n-1)
     = 2 + 4*n(n+1)/2 - 4 - 3n + 3
     = 2n² - n + 1

通項公式：f(n) = 2n² - n + 1

驗證

• n=1：2-1+1=2 ✓
• n=2：8-2+1=7 ✓
• n=3：18-3+1=16 ✓
• n=4：32-4+1=29

算法實現

預計算 f[1..10000]，每查詢 O(1) 輸出。注意 n=10000 時 f(n) ≈ 2×10⁸，需 64 位整數（long long）。

#include 
using namespace std;
int main() {
    vector f(10001);
    for (int i = 1; i <= 10000; i++)
        f[i] = 2LL*i*i - i + 1;
    int T; cin >> T;
    while (T--) {
        int n; cin >> n;
        cout << f[n] << '\n';
    }
    return 0;
}

幾何直覺補充

每條折線 = 兩條射線。第 k 條折線的 2 條射線，每條射線與前 k-1 條折線的 2(k-1) 條射線相交，共 4(k-1) 個交點。一條射線被 m 個點分成 m+1 段，每段劃分一個現有區域，故新增區域數 = 交點數 + 條數 = 4(k-1) + 1（2 條射線共用折線頂點，實際新增段數 = 交點數 + 1）。

總結

本題核心是找規律、推公式、預計算。折線分割平面通過分析新增折線產生的交點數與新增區域數關係，得到簡潔二次多項式 2n² - n + 1。無需幾何庫、無需模擬，純數學推導，O(1) 回答查詢。