折线分割平面-蒲公英云

折线分割平面

/*
 这里我给大家推导以下递推公式的推导步骤：
 上面看到了两条折线 和三条折线的画法，
 我们先来考虑以下两条折线的画法，同样是两条折线为什么图二的就比图一的要多呢，
 我们这里仔细的分析以下两个图的不同，经过观察，
 不难发现，图二的交点比图一的交点多了两个，那是不是这个原因呢？回答是当然!
 那么问题又来了  交点的数目与分割的数量的增加有关系么？
 回答仍然是当然！那么交点数目与分割的数量到底有什么关系呢？我们再来看看图。
经过观察，你可以发现，如果在相邻的两个线段（或者射线）上任选取两个点，
将这两点连线，那么原来的一个区域就会多被分割出来一个。
所以每次所有的交点的之间的区域的数量的增加量就为（交点的数量 - 1） ，
那么交点的数量的增加量到底是多少呢？因为是一个折线（在这里我们可以将其近似考虑成两条直线），
下面大家考虑以下“一条直线与n条直线能有几个交点?"答案必然是n个 ，
所以当一个折线就可以形成2*n（这里的n表示的是n条直线，
所以对于原题的来说一条折线与n条折线的交点数目就为 2*（2*n））个交点，
所以第n条折线所有交点间比第n-1的折线的区域数量增加了4*（n-1） - 1 (交点的数量 - 1 )块，
另外需要注意的是，这是一条折线，所以当与其他的线相交过后必然会在其两端都形成一条射线，
这两条射线也是能够将区域分割开的，所以分割的增加量除了前面交点形成的增加量意外，
还有这两个射线的增加的  2  块。
        所以就有f(n) = f(n-1) + 4 * (n-1) - 1 + 2;
        化简的  f(n) = (n-1) + 4 * n - 3;
*/
#include<stdio.h>
typedef long long ll;
ll a[10050]={1,2,7};
ll f(ll n)
{
    if(n<=2)
    {
        return a[n];
    }
    else
    {
        a[n]=f(n-1)+4*(n-1)-1+2;
    }
    return a[n];
}
int main()
{
    int c;
    ll n;
    while(scanf("%d",&c)!=EOF)
    {
        while(c--)
        {
            scanf("%lld",&n);
            printf("%lld\n",f(n));
        }
    }
    return 0;
}