分割平面，分割空间

** 分割平面，分割空间：** <Excerpt in index | 首页摘要>

转自：http://blog.csdn.net/zy691357966/article/details/41009991

(1) n条直线最多分平面问题

题目大致如:n条直线，最多可以把平面分为多少个区域。    

析:可能你以前就见过这题目，这充其量是一道初中的思考题。但一个类型的题目还是从简单的入手，才容易发现规律。当有n-1条直线时，平面最多被分成了f（n-1）个区域。则第n条直线要是切成的区域数最多，就必须与每条直线相交且不能有同一交点。这样就会得到n-1个交点。这些交点将第n条直线分为2条射线和n-2条线断。而每条射线和线断将以有的区域一分为二。这样就多出了2+（n-2）个区域。   

   故：f(n)=f(n-1)+n   

                =f(n-2)+(n-1)+n   

                ……   

                =f(1)+1+2+……+n   

                =n(n+1)/2+1   

   (2) 折线分平面（hdu2050）   

 根据直线分平面可知，由交点决定了射线和线段的条数，进而决定了新增的区域数。当n-1条折线时，区域数为f（n-1）。为了使增加的区域最多，则折线的两边的线段要和n-1条折线的边，即2*（n-1）条线段相交。那么新增的线段数为4*（n-1），射线数为2。但要注意的是，折线本身相邻的两线段只能增加一个区域。   



 故：f(n)=f(n-1)+4(n-1)+2-1   

                =f(n-1)+4(n-1)+1   

               =f(n-2)+4(n-2)+4(n-1)+2   

               ……   

               =f(1)+4+4*2+……+4(n-1)+(n-1)      

               =2n^2-n+1

(3) 封闭曲线分平面问题

题目大致如设有n条封闭曲线画在平面上，而任何两条封闭曲线恰好相交于两点，且任何三条封闭曲线不相交于同一点，问这些封闭曲线把平面分割成的区域个数。   

 析：当n-1个圆时，区域数为f(n-1).那么第n个圆就必须与前n-1个圆相交，则第n个圆被分为2（n-1）段线段，增加了2（n-1）个区域。



       故： f(n)=f(n-1)+2(n-1)        

                       =f(1)+2+4+……+2(n-1)   

                       =n^2-n+2

例题：

Cake Cutting
Time Limit: 2000 MS Memory Limit: 65536 K
Total Submit: 25(18 users) Total Accepted: 20(18 users) Rating: Special Judge: No
Description
“Happy birthday to you… Happy birthday to you… Happy birthday to Grovyle… Happy birthday to you…”

Today is Grovyle’s birthday and he is going to invite his friends to his birthday party. To have an awesome party, each of the attendants should get one piece of cake. Your job is to help Grovyle invite as many friends as you can.

However, Grovyle’s parents are very mean, and make him use the following rules when cutting his cake:

· There is only ONE cylindrical cake.

· Grovyle cuts the cake n times, each cut being perpendicular to the surface of the cake.

· The i-th cut is a broken line with a[i] vertices.

· The knife is only allowed to intersect the edge of the cylindrical cake at the start and end of the cut.

What is the maximum number of pieces Grovyle could get?

Input
The first line contains an integer T(T ≤ 50), indicating the number of test cases. Each test case begins with an integer n(1 ≤ n ≤ 100), followed by n integers a[i], 0 ≤ a[i]< 400, which indicate the number of vertices in the i-th cut.

Output
For each test case, output “Case #i: “ followed by the maximum number of pieces of cake Grovyle can cut.

Sample Input
5
3 0 0 0
2 1 1
2 1 2
4 0 0 0 1
4 2 2 2 2

Sample Output
Case #1: 7
Case #2: 7
Case #3: 10
Case #4: 14
Case #5: 63

Hint
Illustrations for the first 3 example

Source
“科林明伦杯”哈尔滨理工大学第三届ACM程序设计团队赛
Author
xiaodao

折一次不会交到上一根线，所以sum+=j-1；

Code

#include<iostream>
#include<cmath>
#include<stdio.h>
using namespace std;
int main()
{
int T;
while(~scanf("%d",&T))
{	
int u=1;
while(T--)
{
int i;
int n;

scanf("%d",&n);
int k1,j=1,k,sum=1;
for(i=1;i<=n;i++)
{
scanf("%d",&k);
k1=k;
sum+=j;
j++;
while(k--)
{
sum+=j-1;
j++;
}
sum-=k1;
}
cout<<"Case #"<<u++<<": "<<sum<<endl;
}
}
return 0;
}