解题思路

n 条直线，其中 p 条交于同一点，求最多能分割成多少个区域。

思路：分两段算。

1. p 条共点直线：交于同一点的 p 条直线，把平面分成 2p 个区域（每条直线把一个区域一分为二）
2. 后面的直线：每条新直线和前面所有直线相交，被分成 i 段（交点数+1），每段把原有区域一分为二，所以增加 i 个区域

所以总区域 = 2p + (p+1) + (p+2) + …… + n

举例：n=12，p=5

• 5 条共点直线分 10 个区域
• 第 6~12 条直线分别增加 6、7、8、9、10、11、12 个区域
• 总 = 10 + 63 = 73

参考代码

#include <iostream>
using namespace std;

int main() {
    int n, p;
    cin >> n >> p;

    int total = 2 * p;  // p 条共点直线

    for (int i = p + 1; i <= n; i++) {  // 后续直线
        total += i;
    }

    cout << total;
    return 0;
}

复杂度分析

• 时间复杂度：O(N)
• 空间复杂度：O(1)