牛客小白月赛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;}
美团一面921人在聊
投递腾讯云智研发等公司7个岗位