P5377 [THUPC2019]鸽鸽的分割
Solution I
用欧拉公式推导:
每四个圆上的点会产生两条线段,一个交点,故 。
个点将圆划分为 段圆弧,每两个圆上的点产生一条线段,每四个圆上的点产生的交点将两条线段划分为 部分,故
故 。
注意到圆外还有一个面,答案为 。
Solution II
考虑每增加一个点,下面的弓形被划为 个平面,上面每三个点形成的三角形被划为两个平面,即有:
答案为 。
查看代码
1 2 3 4 5 6 7 8 9
| #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; }
|
Gitalk 加载中 ...