直线，折线，封闭曲线，平面分割区域问题

· · 个人记录

直线分割平面

## 折线分割平面 ### 题目描述 求$n$条折线分割平面的最大数目$(1≤n≤10000)$。比如，一条折线可以将平面分成两部分，两条折线最多可以将平面分成$7$部分。 ![](https://cdn.luogu.com.cn/upload/pic/62426.png ) ### 分析 从图中可以看出，每多出一条折线，都会多出$4*(n-1)$个交点，也就是说会多出$4* (n-1)+1$个平面 所以有递推公式： $f(n)=f(n-1)+4(n-1)+1

    =f(n-2)+4(n-2)+4(n-1)+2
    ……     =f(n-(n-1))+4(n-(n-1))+4(n-(n-2))+…+4(n-1)+n-1
    =f(1) +4(1+2+3+4+....+n-1)+n-1
    =2+4* \frac{(n-1)* n}{2}+n-1
    =2n^2-n+1

代码

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

封闭曲线分割平面

题目描述

有n条封闭曲线画在平面上，而任何两条封闭曲线恰好相交于两点，且任何三条封闭曲线不相交于同一点，求这些封闭曲线把平面分割成的区域个数。 (0<n<1000)

分析

当有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)
    =2+2*(1+2+...+n-1)
    =n^2-n+2

代码

#include<iostream>
using namespace std;
int f[1005];
int main()
{
    int n;
    f[1]=2;
    for(int i=2;i<=1000;i++)
        f[i]=f[i-1]+2*(i-1);
    while(cin>>n)
        cout<<f[n]<<endl;
    return 0;
}

平面分割空间

题目描述

n$个平面最多可以把空间分成多少个区域？$(1≤n≤1000)

分析

首先考虑n条直线能把平面分成几个区域，添加第n条直线时，最佳的画法是与之前的n-1条直线都有交点，且三条及三条以上的直线之间没有共同的交点，这样可以增加n个区域，于是得到\ \ g(n)=g(n-1)+n\ \ \ \ g(0)=1

n$个式子相加可以得到$\ \ P(n)=1+(1+2+…+n)=\frac{n^2+n+2}{2}

接下来考虑空间的情况，同样，为了割法最佳，在添加第n个平面时，需要与之前的n-1个平面都有交线，另外任意两条交线之间两两相交且无重点，这样新添加的这个面就已经被分割成了g(n-1)个区域，而这g(n-1)个区域可以使得整个空间增加g(n-1)块，故得到这样一个式子f(n)=f(n-1)+g(n-1)=f(n-1)+\frac{n*(n-1)}{2}+1\ \ \ \ f(0)=1
将n个式子相加便可以得到

f(n) =\frac{n*(n-1)+(n-1)* (n-2)+…+1* 0}{2}+1* n+1 =\frac{[n^2+(n-1)^2+…+1]-[n+(n-1)+…+1]}{2}+n+1 =\frac{\frac{n(n+1)(2n+1)}{6}-\frac{n(n+1)}{2}}{2}+n+1 =\frac{2n(n+1)(n-1)}{12}+n+1 =\frac{n(n^2-1)}{6}+n+1 =\frac{n^3+5n+6}{6}

代码

#include<iostream>
using namespace std;
int main()
{
    int n;
    while(cin>>n)
        cout<<(n*n*n+5*n+6)/6<<endl;
    return 0;
}