计算几何——平面分割问题¶
平面分割问题其实解法更多的设计递归和动态规划等，但是因为其题面特征比较符合计算几何的特征，所以仍然归类为计算几何类问题。
参考资料：
- 平面分割问题小结
- 《信息学奥赛一本通——基础篇》递推算法例3.7
直线分割平面¶
暂时未在OJ上找到相关例题。
题意：平面上有n条直线，问最多可以将平面划分成多少个区域？（还可以思考一下最多有多少个交点）。
最右策略是线段两两相交，第n条直线和前n-1条直线相交，会产生n-2条线段和2条射线，每个线段或者射线都将原来的区域分成两个部分，则会多出来n-2+2= n个区域，递推关系a_n = a_{n - 1} + n，动态规划求解即可，注意大数的情况。
扩展：《信息学奥赛一本通——基础篇》递推算法例3.7，同一平面内的n条直线，已知有p条直线相交于一点，问n条直线最多分割出多少个平面区域？
首先考虑p条直线交于一点，则会分出2p个区域，设余下的n-p = m条直线，最优策略是与前面的直线两两相交，仍然按照上面的思路，则：
$$
a_p = 2 * p \
a_{p + 1}= a_p + p + 1 \
a_{p + 2} = a_{p + 1} + p + 2 \
\cdots
a_{p + m} = a_{p + m - 1} + m
$$
然后递推求解即可。
折线分割平面¶
典型题目比如HDU 2050。
我们看到过很多直线分割平面的题目，今天的这个题目稍微有些变化，我们要求的是n条折线分割平面的最大数目。比如，一条折线可以将平面分成两部分，两条折线最多可以将平面分成7部分，具体如下所示。
假设前n-1个折线已经构成最优解，第n条折线的策略是每条线都和前n-1条折线的两条边相交，则肯定会构成2 * (2*(n-1) - 1)条线段，和多出来的一个尖角构成的区域，以及两条射线分割出来的区域，所以是：
$$
a_n = a_{n - 1} + 4(n - 1) - 2 + 1 + 2 = 4n-3\
\therefore a_n = 2n^2 - n + 1\
$$
#include <iostream>
#include <vector>
#include <cmath>
#include <string>
#include <climits>
#include <cstdio>
#include <queue>
#include <stack>
#include <map>
#include <algorithm>
using namespace std;
int main()
{
std::ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int caseNum; cin >> caseNum;
while (caseNum--) {
int n; cin >> n;
cout << (2 * n * n - n + 1) << endl;
}
return 0;
}
椭圆分割平面¶
《一本通》第二部分第三章的3.平面分割问题。
题意：设有n条封闭曲线画在平面上，而任何两条封闭曲线恰好相交于两点，且任何三条封闭曲线不相交于同一点，问这些封闭曲线把平面分割成的区域个数。
第n个封闭图形会和前n-1个产生两个交点，从而多出两个区域，递推关系：
$$
a_n = a_{n - 1} + 2(n - 1)
$$
三角形分割平面¶
典型题目如HDU 1249.
题意：用N个三角形最多可以把平面分成几个区域?
当n=1的时候，最多分成两个区域，当n = 2的时候，最多分成8个区域。规律其实就是后面的每条线和前面n-1个三角形的两边相交，三个边都遵循这个规律，于是得到递推关系：
$$
a_n = a_{n - 1} + 3\times(2\times (n- 1 ) - 1) + 3 \
a_n = 3n^2 - 3n + 8
$$
#include <iostream>
#include <vector>
#include <cmath>
#include <string>
#include <climits>
#include <cstdio>
#include <queue>
#include <stack>
#include <map>
#include <algorithm>
using namespace std;
int main()
{
std::ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int caseNum; cin >> caseNum;
while (caseNum--) {
int n; cin >> n;
cout << (3 * n * n - 3 * n + 2) << endl;
}
return 0;
}