Codeforces Round #313 Div.2 C：六邊形分割正三角形計數

問題描述

給定順時針六條邊長 a1..a6 的凸六邊形，保證可由單位正三角形拼成。求包含多少個單位正三角形。

幾何分解洞察

六邊形可視為「上等腰梯形 + 中間平行四邊形 + 下等腰梯形」的組合。旋轉六邊形使 a1 為頂邊，則必有 a2+a6 = a3+a5（對邊平行等長）。此時：

• 上梯形腰長 = min(a2, a6)
• 下梯形腰長 = min(a3, a5)
• 中間平行四邊形邊長 = |a2-a6|（即 |a3-a5|）

面積計算公式

單位正三角形面積為 1。等腰梯形由若干行三角形組成，第 k 行有 2*(base+k)-1 個。平行四邊形每行 2*base 個，共 height 行。通過累加三部分面積得答案。

代碼實現

int a[10];
int main() {
    for (int i=1;i<=6;i++) scanf("%d",&a[i]);
    // 旋轉直到 a2+a6 == a3+a5
    for (int r=0;r<3;r++) {
        if (a[2]+a[6] == a[3]+a[5]) break;
        int t=a[1];
        for (int i=1;i<6;i++) a[i]=a[i+1];
        a[6]=t;
    }
    int x = min(a[2],a[6]), y = min(a[3],a[5]);
    int L = abs(a[2]-a[6]);
    long long sum = 0;
    int cnt = a[1];
    // 上梯形
    for (int i=1;i<=x;i++) sum += 2LL*cnt+1, cnt++;
    // 平行四邊形
    sum += 2LL*cnt*L;
    cnt--;
    // 下梯形
    for (int i=1;i<=y;i++) sum += 2LL*cnt+1, cnt--;
    printf("%lld\n", sum);
    return 0;
}

關鍵點

• 旋轉找到對稱軸，保證分解合法。
• 面積累加利用等差數列求和，long long 防溢出。
• 樣例驗證：1 1 1 1 1 1 → 正六邊形，面積 6。

總結

此題將幾何分割轉化為代數累加，核心在於識別「對邊平行」條件並正確旋轉。代碼極短，思維優美，是幾何與組合數學結合的典範。