题目

Problem Description

n 条折线分割平面的最大数目

Input

输入数据的第一行是一个整数C,表示测试实例的个数，然后是C 行数据，每行包含一个整数 n(0 < n <= 10000),表示折线的数量

Output
对于每个测试实例，请输出平面的最大分割数，每个实例的输出占一行

Sample Input
2
1
2

Sample Output
2
7

数学知识

直线

• N 条相交的直线最多能把平面分割成几块

当添加第n条直线时，为了使平面最多，则第 n 条直线要与前面 n-1 条直线都相交，并且没有任何三条线交于一个点

这样，第 n 条直线一共有 n-1 个交点

我们知道，增加 n 个交点，则增加 n+1 个平面

所以 n 条直线分割平面最大数是 1 + 1 + 2 + 3 + ... + n = (n2 + n + 2) / 2

平行线

• 把直线改为平行线，最多能把平面分割成几块

当第 N 次添加时，前面已经有 2N-2 条直线了

按我们上面讨论的知道，第 N 次添加时，第 2N-1 条直线和第 2N 条直线各能增加 2(n-1)+1 个平面

所以第 N 次添加增加的面数是 2[2(n-1) + 1] = 4n - 2 个

因此，总面数应该是 2n² + 1

折线

• 把平行线改为折线，最多能把平面分割成几块

通过观察可以发现，每当一组平行线相交后，就会减少一个面
因此，n 条折线分割平面，自然就是上面求的的平行线分割平面数减去 n，即 2n² + 1 - n

代码

#include <cstdio>
int main() {
    int n, val;
    scanf("%d", &n);
    while (n--) {
        scanf("%d", &val);
        printf("%d\n", 2 * val * val + 1 - val);
    }
}