直线折线分割平面问题

1.对于直线分割问题

明确一个前提定理：直线分割新增加的区块等于新增加的交点数+1

定理理解：比如现在添加第n条直线，那么就说明现在已经有n-1条直线了，那么要添加的第n条直线最理想状态

自然是和之前的n-1条直线都相交，即增加n-1个交点。这n-1个交点让第n条直线被分割成为n-2条线段+2条射线（边缘）

利用想象可以理解由于被分割出了n-2条线段+2条射线，所以会增加n个区块，即新增交点数+1

2.对于折线分割问题

我以HDU2050为例子

http://acm.hdu.edu.cn/showproblem.php?pid=2050

这种折线可以看成是两个起点相同的射线构成的

假设增加第n条折线，那么先前已经有n-1条折线了，也就是2（n-1）条射线，由于折线由两条射线组成，那么第n条折线

也可看作是两条射线，分别交之前的2（n-1）条射线，从而增加2*2（n-1）个交点，由定理可知，增加了4（n-1）+1个区块

所以就得出了递推公式 block[i]=block[i-1]+4*(n-1)+1;

#include <iostream>
using namespace std;
long long int block[10010];
int main()
{
    int n;
    cin >> n;
    block[0] = 1;
    for (int i = 1; i <= 10000; i++)
    {
        block[i] = block[i - 1] + 4 * (i - 1) + 1;
    }
    for (int i = 1; i <= n; i++)
    {
        int m;
        cin >> m;
        cout << block[m] << endl;
    }
    return 0;
}

直线折线分割平面问题

原文：https://www.cnblogs.com/Knightero/p/13209751.html