【题解】平面分割

题目：平面分割

写在前面:

这个题比较难想，最好是结合画图来看。

思路:

• n个圆可以将一个平面分割为多少部分:
  除第一个圆外,每添加一个圆都会将平面额外分割2*(n-1)部分
  f(1) = 2
  f(2) = f(1) + 2 * (n - 1) = 4
  f(3)= 8
  f(n) = f(n - 1) + 2 * (n - 1)
  f(n) = f(n - 2) + 2 * (n - 2) + 2 * (n - 1)
  f(n) = 2 + 2 * 1 + 2 * 2 + … + 2 * (n - 1) = 2 + 2 * (1 + 2 + 3 + … + n - 1)
  = 2 + 2 * ((1 + n - 1) * (n - 1)) / 2
  = 2 + n * (n - 1);

• m个直线可以将一个平面分割为几部分:
  除第一条直线外,每额外添加一条直线都会将平面额外分割n部分
  h(1) = 2
  h(2) = 4
  h(3) = 7
  h(n) = 2 + 2 + 3 + 4 … + n
  = 1 + (1 + n) * n / 2

• n个圆和m个直线共可以将平面分为几个部分:
  n个圆0条线:g(n,0)=f(n)= 2 + n * (n - 1);
  n个圆1条线:这条直线可以分割它与所有圆交点个数个部分,每个圆可产生2个交点,也即增多2n个部分
  g(n,1)=2 + n * (n - 1)+2n;
  n个圆2条线:第二条线同样可以产生2n个部分,除此之外还将与第一条直线相交分割一个部分
  g(n,2)=g(n,1)+2n+2

• 最终公式：

  g(n,m)=2+n*(n-1)+2nm+(2+m)*(m-1)/2

代码:

#include<map>
#include<queue>
#include<cmath>
#include<string>//使用to_string必须加该头文件
#include<vector>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define ll long long 
#define itn int
const int array_size = (int)1e6 + 50;
const int INF = 0x3f3f3f3f;
using namespace std;

int main()
{
	int m = 20, n = 20;
	cout << 2 + n * (n - 1) + 2 * n * m + (2 + m) * (m - 1) / 2 << endl;
	return 0;
}