HDU 2050 折线分割平面【递推】

题目链接

题目描述：

求的是 n (0 < n ≤ 10000) 条折线分割平面的最大数目。比如，一条折线可以将平面分成两部分，两条折线最多可以将平面分成7部分，具体如下所示。

关于直线分割平面：

1. 每次加一条直线分割平面，增加到第 n 条直线时，跟之前的直线最多有 n - 1 个交点，这 n - 1 交点就像把第 n 条直线分成了 (n - 1) + 1段，所以增加了 (n - 1) + 1个平面。
2. 若每次增加两条直线，假设现在是第 n 次，我们将两条直线分开加，第一条与之前的直线最多有2 * (n - 1) 个交点，增加 2 * (n - 1) + 1 分隔面，第二条与之前的直线最多有 2 * (n - 1) + 1 个交点，所以增加 2 * (n - 1) + 1 + 1 个分隔面，所以每次总共增加 4 * n - 1个分割面。

对于折线分割平面：

1. 折线同理直线，一条折线与另一条折线最多有 4 个交点，所以添加第 n 条折线时，与之前最多有 4 * (n - 1) 个交点，所以新增 4 * (n - 1) + 1 个分隔面。

AC Codes：

#include <iostream>
#include <vector>
#include <queue>
#include <stack>
#include <set>
#include <map>
//#include <unordered_set>
//#include <unordered_map>
#include <deque>
#include <list>
#include <iomanip>
#include <algorithm>
#include <fstream>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <cstdlib>
//#pragma GCC optimize(2)
using namespace std;
typedef long long ll;
//cout << fixed << setprecision(2);
//cout << setw(2);
const int N = 2e5 + 6, M = 1e9 + 7, INF = 0x3f3f3f3f;int main() {
    //freopen("/Users/xumingfei/Desktop/ACM/test.txt", "r", stdin);ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);int t;cin >> t;while (t--) {
    int n;cin >> n;long long ans = 2, now = 1;for (int i = 2; i <= n; i++) {
    ans += 4 * now + 1;now++;}cout << ans << '\n';}return 0;
}