Blog of RuSun

OneProblemIsDifficultBecauseYouDontKnowWhyItIsDiffucult

P5377 [THUPC2019]鸽鸽的分割

P5377 [THUPC2019]鸽鸽的分割

Solution I

用欧拉公式推导:

F=EV+2

每四个圆上的点会产生两条线段,一个交点,故 V=n+(n4)

n 个点将圆划分为 n 段圆弧,每两个圆上的点产生一条线段,每四个圆上的点产生的交点将两条线段划分为 4 部分,故 E=n+(n2)+2(n4)

F=2+(n2)+(n4)

注意到圆外还有一个面,答案为 F1

Solution II

考虑每增加一个点,下面的弓形被划为 n1 个平面,上面每三个点形成的三角形被划为两个平面,即有:
fi=fi1+(n13)+n1
答案为 1+n(n1)2+(n14)

查看代码
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 加载中 ...