折线分割平面

折线分割平面

Time Limit: 1000MS Memory limit: 32768K

题目描述

我们看到过很多直线分割平面的题目，今天的这个题目稍微有些变化，我们要求的是n条折线分割平面的最大数目。比如，一条折线可以将平面分成两部分，

Input 
输入数据的第一行是一个整数C,表示测试实例的个数，然后是C 行数据，每行包含一个整数n(0< n<=10000),表示折线的数量。 
Output 
对于每个测试实例，请输出平面的最大分割数，每个实例的输出占一行。 
Sample Input 
2 
1 
2 
Sample Output 
2 
7

分析

直线分割平面

已有(n-1)条直线，再添加一条直线，最多有n-1个交点，增加了n个平面。

两条平行线分割平面

已有(n-1)组两条平行线，再添加一组平行线，平行线的其中一条和其他的2*(n-1)条直线，有2*(n-1)个交点，增加了2*(n-1)+1个平面，所以添加一组平行线，增加2*(2*(n-1)+1)个平面，整理下就是4*n-2个平面

折线分割平面

将平行线的两端连起来，形成折线，会发现本来被为3个平面的，会合成2个平面，所以添加一条折线增加 
2*(2*(n-1)+1)-1个平面，整理下就是4*n-3个平面。所以f(n) = f(n-1) + 4*n-3。

#include<iostream>
using namespace std;
int main()
{
	int t,n,i;
	long long s[10001];
	s[0]=1;
	s[1]=2;
	s[2]=7; 
	cin>>t;
	while(t--)
	{
		cin>>n;
		for(i=3;i<=n;i++)
		{
			s[i]=s[i-1]+4*i-3;
		}
		cout<<s[n]<<endl;
	}
	return 0;
 }