题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=1913

题意:


对于已经确定 3 个点在圆上的情况,由于剩下的点都是互相独立的,我们只需要枚举每一个点作为第四个点,确定是否在圆上,求和除以总方案数即可。
那么四个点构成一个四边形,我们考虑可能组成的所有四边形
1. 凹四边形
很显然,凹进去的那个点不可能作为圆上点,只能为答案带来 1 的贡献
2. 凸四边形
由于四点不共圆,可以认为两组对角一组和大于 180 度,一组小于 180 度,大于 180 度的两个点分别在圆内是仅有的合法情况,可以带来 2 的贡献 (由于无法显示汉字,记录 ao 为凹,tu 为凸
那么\(ans=\frac{num_{凹}+2*num_{凸}}{C(n,3)}+3\)
四边形的总数是 C(n,4) 那么\(ans=\frac{num_{凹}+2(C(n,4)-num_{凸})}{C(n,3)}+3\)
只需要求 num_凹 即可了
这是一个典型的问题 我们考虑枚举确定凹四边形凹进去的那个点 i
然后将它作为原点,对其它点按极角序排序,那么\(num_{凹}=C(n-1,3)-num_{凸'}\)
枚举凹点位于的那个三角形上的一个点 j
找到一个点 k 使得 ij 与 ik 夹角小于 180 度且尽可能靠近 180 度,那么这个夹角里的点都不可能作为最后一个点了 这是 C[k-j][2] 的...

 


一个非常弱的准退役OIER