MT1069 圆切平面

n个圆最多把平面分成几部分？输入圆的数量N，问最多把平面分成几块。比如一个圆以把一个平面切割成2块。 不考虑负数，0或者其他特殊情况。

格式

输入格式：输入为整型

输出格式：输出为整型

样例 1

输入：

2

输出：

4

方法1：利用点-棱-面公式：v-e+f=2。

其中v为交点。此时有n个圆。若随机两两相交，则共有n*Cn2=n*(n-1)个交点。

e为棱数，即圆弧数。两个圆相交最多有两个交点，即各自被分成两段圆弧。此时有n个圆，对于每一个圆，有剩余(n-1)个圆与它相交，即此时弧最多为2*(n-1)，所以n个圆最多有n*2*(n-1)条弧。

v-e+f=2，解方程得f=2-v+e，即f=2-(n*(n-1))+n*2*(n-1) ，f=n^2-n+2。

代码：

#include <iostream>
using namespace std;
int main()
{
  int n;
  cin >> n;
  cout <<n*n-n+2;
  return 0;
}

方法2：

设n个圆最多可以把平面分成S(n)个部分，则S(1)=2，S(2)=4。则n-1个圆可以把平面分成S(n-1)个部分，此时加入第n个圆，这个圆与前n-1个圆最多有2*(n-1)个交点（因为这个圆每次与其他圆相交，必有进圆和出圆两步，所以n-1中的每个圆都会有2个交点，总起来是2*(n-1)个）。

所以可以得到递推关系式：S(n)=S(n-1)+2*(n-1)，即S(n)-S(n-1)=2*(n-1)。

再用高中知识解，即可得到S(n)=n^2-n+2。

代码和方法1一样。