2050 折线分割平面

type

status

date

slug

summary

题目

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

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

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

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

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

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

所以 n 条直线分割平面最大数是 1 + 1 + 2 + 3 + ... + n = (n² + 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