P5377 [THUPC2019]鸽鸽的分割

P5377 [THUPC2019]鸽鸽的分割

Solution I

用欧拉公式推导：

$F = E - V + 2$

每四个圆上的点会产生两条线段，一个交点，故 $V = n + \binom n 4$ 。

$n$ 个点将圆划分为 $n$ 段圆弧，每两个圆上的点产生一条线段，每四个圆上的点产生的交点将两条线段划分为 $4$ 部分，故 $E = n + \binom n 2 + 2\binom n 4$

故 $F = 2 + \binom n 2 + \binom n 4$ 。

注意到圆外还有一个面，答案为 $F - 1$ 。

Solution II

考虑每增加一个点，下面的弓形被划为 $n - 1$ 个平面，上面每三个点形成的三角形被划为两个平面，即有：
$$
f _ i = f _ {i - 1} + \binom {n - 1} 3 + n - 1
$$
答案为 $1 + \frac {n(n - 1)} 2 + \binom {n - 1} 4$ 。

查看代码

#include <cstdio>
using namespace std;
int main ()
{
    int n;
    while (~scanf("%d", &n))
        printf("%d\n", 1 + n * (n - 1) / 2 + n * (n - 1) * (n - 2) * (n - 3) / 24);
    return 0;
}