1249 三角形.cpp

ACM 威士忌部分答案

/*
1249 三角形
Time Limit : 1000 ms  Memory Limit : 32768 K  Output Limit : 256 K

GUN C++
*/
/*
组合数学——分区域问题从简

1、平面上有n条直线，其中无两线平行也无三线共点，求平面被这n条直线分成多少个不连通的区域？
解：采用递推方法（设n条如此之直线分平面l（n）个不连通区域）：
当只有1条直线时平面分成2个区域；
看n条直线的情形：去掉第n条直线剩下的n-1条直线分平面l（n-1）个不连通区域，加上第n条直线时，
其与这n-1条直线相交于n-1个点，将第n条直线分成n段，每段分原来的区域为两个较小的区域，
从而l（n）应该等于原来的l（n-1）个加上后来分割后多出来的n个，即是：
l（n）=l（n-1）+n
    由上述递推关系和初值可很快解出：l（n）=l（n-1）+n=l（n-2）+（n-1）+n=...=l（1）+2+...+n
                                             =1+n*（n+1）/2
答：平面上两两相交，但无三条共点的直线分平面 1+n*（n+1）/2个区域。
[附注]取l（n）表示line，下文的c（n）表示circle，t（n）表示triangle.

2、平面上有n（n〉=2）个圆，任何两个圆都相交但无3个圆共点，求这n个圆把平面划分成多少个不连通的区域？
解：同样采用递推方法（设n条如此之圆分平面c（n）个不连通区域）：
当只有一个圆时平面分成2个区域；
看n个圆的情形，和上述直线情形一样考虑，第n个圆与前n-1个圆交于2*（n-1）个点，但要注意比原来还是
多出2*（n-1）个区域（圆的循环），于是：c（n）=c（n-1）+2*（n-1）
求解有n^2-n+2。

3、三角形呢，用n个三角形最多可以把平面分成几个区域?
解：同上，不想写了。滚蛋吧！
        t(1)=2
        t（n）=t（n-1）+6*（n-1）
*/
#include <iostream.h>
using namespace std;

const int tMax=10000;
const int nMax=10000;

int main()
{
    int t,n,ca,cb;
    int tn;
    cin>>t;
    for(ca=0;ca<t;ca++)
    {
        cin>>n;
        tn=2;
        for(cb=2;cb<=n;cb++)
        {
            tn+=6*(cb-1);
        }
        cout<<tn<<endl;
    }
    return 0;
}