题解 A347.平面切割2

用 a[i] 表示 i 对平行直线最多能将这个圆分割成的部分数，易得：
当 i=1 时，a[1]=3，当 i=2 时，a[2]=9

回忆直线分割圆的思路：要分割成最多部分，则新加的直线要与之前的直线都要分别交于不同点才可以。

对于平行线也是一模一样的。

第 i 对平行线的 2 条直线和前 i–1 对平行线都有不同的交点，且交点数为 2×(i−1)

i>=2时，a[i]=a[i−1]+(交点数+1)×2
代入得： a[i]=a[i−1]+((i−1)×2+1)×2=a[i−1]+4×i−2

1、定义变量n,进行输入,定义数组用来存储

2、初始条件,一对平行线最多能将圆分割成3部分

3、递推式求a[n]

4、输出答案

#include <iostream>
using namespace std;
long long a[10010];
int main()
{
	//1、定义变量n,进行输入,定义数组用来存储 
	int n;
	cin >> n;
	//2、初始条件,一对平行线最多能将圆分割成3部分 
	a[1] = 3;
	//3、递推式求a[n] 
	for(int i = 2; i <= n; i++)
		a[i] = a[i - 1] + 4 * i - 2;
	//4、输出答案 
	cout << a[n];
	return 0;
}