三角形

Time Limit: 2000/1000 MS (Java/Others)????Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 3238????Accepted Submission(s): 2224

Problem Description 用N個三角形最多可以把平面分成幾個區(qū)域?

?

Input 輸入數(shù)據(jù)的第一行是一個正整數(shù)T(1<=T<=10000),表示測試數(shù)據(jù)的數(shù)量.然后是T組測試數(shù)據(jù),每組測試數(shù)據(jù)只包含一個正整數(shù)N(1<=N<=10000).

?

Output 對于每組測試數(shù)據(jù),請輸出題目中要求的結(jié)果.

?

Sample Input 2 1 2

?

Sample Output 2 8

?

Author Ignatius.L

?

Recommend Ignatius.L 題目結(jié)構(gòu)很簡單，主要是分析三角形個數(shù)m與最大化分區(qū)域個數(shù)之間的關(guān)系，記做S(m)。 當(dāng)m=1,S(m)=2,三角形內(nèi)1塊，三角形外一1， 當(dāng)m=2,S(m)=8,呈六芒星狀，六芒星內(nèi)有7塊，外有1塊，。 觀察得，新增幾個交點(diǎn)，就增加幾個區(qū)域。 當(dāng)m=1,S(m)=2，交點(diǎn)數(shù)為0,S(1)=2； 當(dāng)m=2,S(m)=8，交點(diǎn)數(shù)為6,S(2)=2+6； 再畫出m=3的情況，可以總結(jié)出每個圖形總比上個圖形新增6(m-1)個交點(diǎn)， 即S(m)=S（m-1）+6（m-1）； 根據(jù)求和公式 S(m)=3m(m-1)+2; #include<stdio.h> int main() {int n;scanf("%d",&n);while(n--){int m;scanf("%d",&m);printf("%d\n",3*m*(m-1)+2);} }

?

轉(zhuǎn)載于:https://www.cnblogs.com/TheLaughingMan/archive/2013/03/26/2983293.html

總結(jié)

以上是生活随笔為你收集整理的[解题报告]HDU 1249 三角形的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。