puzzle（006.1）平面划分问题HDU 1249 三角形
目录
CSU 2059 Water Problem（Z字形分隔平面）
一，连续空间划分问题
1，1维——线段 or 直线
n个点可以把线段或者直线分成多少段？
答案是 n+1
2，2维——圆形 or 整个平面
（1）n个直线把圆或者平面分成多少块？
答案是（1+2+3+......+n）+1 = n(n+1)/2+1
（2）圆上的n个点，两两连接成的n(n-1)/2条弦最多可以把圆分成多少块？
思路：单点发出的n-1条弦被其他弦分割形成的分割点的个数是1*(n-3)+2*(n-4)+...+(n-4)*2+(n-3)*1=(n-1)(n-2)(n-3)/6
所以答案是
即n(n-1)(n-2)(n-3)/24+n(n-1)/2+1
3，3维——球形 or 整个空间
（1）n个平面把球形或者空间分成多少块？
答案是
（2）在matrix67的博客中还有这么一个问题，n刀可以把甜甜圈切成多少块？
通过拓扑变换，可以推导出，n刀可以把甜甜圈切成多少块其实就是n+1刀可以把球形分成多少块。所以答案是
4，k维——整个k维空间
通用问题，n个k-1维的刀，可以把一个k维的无穷空间切成多少块？
递推式是
例如，
即，n刀可以把一个无限的三维空间切成块。
二，OJ实战
HDU 1249 三角形
题目：
Description
用N个三角形最多可以把平面分成几个区域?
Input
输入数据的第一行是一个正整数T(1<=T<=10000),表示测试数据的数量.然后是T组测试数据,每组测试数据只包含一个正整数N(1<=N<=10000).
Output
对于每组测试数据,请输出题目中要求的结果.
Sample Input
2
1
2
Sample Output
2
8
解释一下网上到处飞的递推式f(n)=f(n-1)+(n-1)*6是怎么来的。
这个问题其实和n条直线可以把平面分成多少个部分是差不多一样的。
对于直线的问题，递推式是f(n)=f(n-1)+n
也就是说，从n-1条直线，变成n条直线，多了n块。
为什么就刚好是n呢？因为，一条直线可以被n-1条直线分成n段，而每一段，都恰好对应着从n-1条直线变成n条直线时会有1块变成2块，于是整体增加了n块。
对于三角形的问题，道理是一样的。
一个三角形（注意，这里指的是三条边构成的曲线）可以被n-1个三角形分成(n-1)*6段，于是便得到了递推式。
所以f(n)=3 * n*(n - 1) + 2
代码：
#include<iostream>
using namespace std;
int main()
{
int k, n;
cin >> k;
while (k--)
{
cin >> n;
cout << 3 * n*(n - 1) + 2 << endl;
}
return 0;
}HDU 2050 折线分割平面
题目：
我们看到过很多直线分割平面的题目，今天的这个题目稍微有些变化，我们要求的是n条折线分割平面的最大数目。比如，一条折线可以将平面分成两部分，两条折线最多可以将平面分成7部分，具体如下所示。
Input
输入数据的第一行是一个整数C,表示测试实例的个数，然后是C 行数据，每行包含一个整数n(0<n<=10000),表示折线的数量。
Output
对于每个测试实例，请输出平面的最大分割数，每个实例的输出占一行。
Sample Input
2
1
2
Sample Output
2
7
这个问题的本质，和直线分割平面问题是一样的。
每增加1个折线，增加的平面区域的数目等于增加的交点的数目加1
每2个折线都可以有4个交点，如此便得到公式
代码：
#include<iostream>
using namespace std;
int main()
{
int a;
cin >> a;
while (cin >> a)cout << a*a * 2 - a + 1 << endl;
return 0;
}51Nod 1104 直线分割圆
圆上有N个点，每个点和其他所有点之间都有直线相连。并且任意3线不共点。计算这些直线把圆分割所得的区域的数量K。
例如：N = 2，K = 2，N = 3，K = 4。由于结果可能会很大，输出K Mod (10^9 + 7)的结果。
Input
输入：1个数N。(2 <= N <= 10^9)
Output
输出数量 Mod 10^9 + 7
Sample Input
2
Sample Output
2
#include<iostream>
using namespace std;
int main()
{
long long n,p=1000000007;
cin>>n;
long long x=n*(n-1)/2%p,y=(n-2)*(n-3)/2%p;
long long z=x*y%p*(p+1)/6%p+x+1;
cout<<z%p;
return 0;
}CSU 1284 Cutting Cake
题目：
Description
一个蛋糕切N刀，最多能得到多少块？切的过程中不能改变任意一块蛋糕的位置。
Input
输入数据的第一行包含一个整数T (1 <= T <= 100)，表示接下来一共有T组测试数据。
每组测试数据占一行，包含一个整数N (1 <= N <= 100)，含义同上。
Output
用一行输出一个整数，表示上述问题的答案。
Sample Input
3
2
3
4
Sample Output
4
8
15
代码：
#include<iostream>
using namespace std;
int main()
{
int t, n;
cin >> t;
while (t--)
{
cin >> n;
cout << (n*n - 1)*n / 6 + n + 1 << endl;
}
return 0;
}CSU 2059 Water Problem（Z字形分隔平面）
题目：
Description
一条‘Z’形线可以将平面分为两个区域，那么由N条Z形线所定义的区域的最大个数是多少呢？每条Z形线由两条平行的无限半直线和一条直线段组成
Input
首先输入一个数字T（T<100），代表有T次询问 每次询问输入一个数字N（N<1e8），代表有N条Z形线
Output
对于每次询问，在一行输出N条‘Z’形线所能划分的区域的最大个数为多少
Sample Input
2
1
2
Sample Output
2
12
思路：
首先考虑一个类似的问题：
有N组直线，每组都由3条平行的直线构成，3条直线的间距可以调整。
那么N组直线最多划分出多少个区域？
这个问题就很容易求出来，3n（3n-1）/2+1
本题的答案，就是把每组3条平行直线变成Z，也就是在3n（3n-1）/2+1的基础上再减2n即可
代码：
#include<iostream>
using namespace std;
int main()
{
long long a;
cin >> a;
while (cin >> a)cout << (a * 9 - 7)*a / 2 + 1 << endl;
return 0;
}三，对称之美
最强大脑同款项目。
练习模式
（3）
（8）
比赛模式
简单
普通
困难
前面很多地方是随便试的，最后这块有个白格子没覆盖，不好解决。
策略
文章来源: blog.csdn.net，作者：csuzhucong，版权归原作者所有，如需转载，请联系作者。
原文链接：blog.csdn.net/nameofcsdn/article/details/126312230
- 点赞
- 收藏
- 关注作者
评论（0）