480
HDU 1249 三角形
三角形Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 4150 Accepted Submission(s): 2792
Problem Description
用N個三角形最多可以把平麵分成幾個區域?
Input
輸入數據的第一行是一個正整數T(1<=T<=10000),表示測試數據的數量.然後是T組測試數據,每組測試數據隻包含一個正整數N(1<=N<=10000).
Output
對於每組測試數據,請輸出題目中要求的結果.
Sample Input
2
1
2
Sample Output
2
8
思路：（參考 https://hi.baidu.com/matrixwhisper/item/6bfe48522351e0d19e266717 ）
N個三角形將平麵分割成多少區域？先成簡單的情況入手：當n=1時，S(1) = 2; 當n=2時，S(2) = 8; 當n=3時，S(3)=20; 當n=4時，S(3)=20;當n=4時，S(4)=38:
當n=2時，新增的三角形與原有的三角形有了六個交點，即每條邊兩個交點，也就產生了六個新增的區域：同理n=3,4..；由於作圖比較難，所以就不畫出來了。大家可以自己動手做。
遞推式：
公式：
這類總結一下：對於這類題目，我們先從簡單的入手，抓住新增的圖形與原有的圖形產生的點的個數，從而找到與新增的區域的個數的關係！
#include<stdio.h>
int main()
{
int i,j,n,m;
scanf("%d",&n);
while(n--)
{
scanf("%d",&m);
printf("%d\n",3*m*(m-1)+2);
}
return 0;
}
最後更新：2017-04-03 12:55:01