竞赛讨论区 > 牛客小白月赛5F圆的公式推导 组合数 欧拉公式
头像
Stump
编辑于 2018-07-28 09:02
+ 关注

牛客小白月赛5F圆的公式推导 组合数 欧拉公式

题目大意
一个圆上有n个点,在n个点中间两两连边,求最多产生多少个区域?
视频讲解:
3B1B视频讲解
力推3B1B视频
思路:
首先在圆上去n个点,
要是n个点产生的区域数最大,
就必须是任意3条直线不交于一点。
也就是园内任意一点最多只有两条直线经过。
在圆上的n个点会连出C(n,2)条直线。
任意一个圆内交点都可以有圆上四点构成的四元组唯一对应,
那么无序四元组的个数为C(n,4),也是交点个数。
如果把圆看成一张图(圆弧也是边),
点由直线交点和圆上的点构成,
直线交点数量为C(n,4),圆上交点数量为n。
那么点数有n+C(n,4)。
边由圆弧和直线上被交点分割成的若干小段构成,
圆弧数量为n,
有n条直线,m个交点。
考虑每增加一个交点,就会产生新边数量为2(自己画图YY一下)
原来有n条直线,有n条边,
每有一个交点,就会使其中两条直线上的边数加2,
m个交点,就加了2m条边,所以总共n+2m条边。
被分割成的若干边的数量为C(n,2)+2C(n,4)。
边数有C(n,2)+2C(n,4)+n。
根据欧拉公式F-E+V=2(二维和三维一样适用)有
F:面数(区域数)E:边数 V:点数
E=C(n,2)+2C(n,4)+n
V=n+C(n,4)。
F=E-V+2
=C(n,4)+C(n,2)+2
扣掉圆外区域
答案为C(n,4)+C(n,2)+1
复杂度 O(1)
内容板块
数学:组合数
图论:欧拉公式
#include<cstdio>
#include<algorithm>
#include<iostream>
int n;
int main(){
    while(~scanf("%d",&n))
        cout<<1+1ll*n*(n-1)/2+1ll*n*(n-1)/2*(n-2)/3*(n-3)/4<<endl;
    return 0;
}

全部评论

(2) 回帖
加载中...
话题 回帖

等你来战

查看全部

热门推荐