题目链接: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;
}
最后修改:2020 年 12 月 22 日 07 : 56 AM