题目链接：LOJ 6615

牛牛有一块蛋糕，他想把蛋糕分给小朋友们。蛋糕一开始是圆形的，牛牛会在圆周上选择 $n$ 个不重合的点，将这几个点两两用线段连接。这些线段将会把蛋糕分成若干块。

现在，牛牛想知道，蛋糕最多会被分成多少块，请你告诉他答案。

数据范围：$0 \le n \le 64$。

Solution

最优情况下，不存在三条线交于同一点。

根据欧拉公式 $V - E + F = 2$ 可以得到 $F = E - V + 2$。

在圆上的四个不同的点可以新产生一个交点，加上选出的 $n$ 个点，则 $V = \binom{n}{4} + n$。

在圆上的两个不同的点可以连出一条线段，每个交点又会贡献 $2$ 条线段，加上圆上的 $n$ 段弧，则 $V = 2\binom{n}{4} + \binom{n}{2} + n$。

由于圆外的部分不算在答案内，故需要减去 $1$，答案为 $E - V + 1 = \binom{n}{4} + \binom{n}{2} + 1$。

时间复杂度：$\mathcal O(1)$。

Code

#include <bits/stdc++.h>

int main() {
    int n;
    for (; scanf("%d", &n) == 1; ) {
        printf("%d\n", 1 + n * (n - 1) / 2 + n * (n - 1) * (n - 2) * (n - 3) / 24);
    }
    return 0;
}