题目链接：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] 的...
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 |
#include <cmath> #include <queue> #include <cstdio> #include <cstring> #include <cstdlib> #include <iomanip> #include <iostream> #include <algorithm> #define Pi acos(-1.0) #define N 1510 #define ll long long using namespace std; inline int read() { int x=0,f=1;char ch=getchar(); while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();} while(ch<='9'&&ch>='0'){x=x*10+ch-'0';ch=getchar();} return x*f; } struct zgz { int x,y; }p[N]; double a[N<<1]; ll C[N][5]; int n; ll tmp1,tmp2; int main() { n=read(); for(int i=1;i<=n;i++) p[i].x=read(),p[i].y=read(); for(int i=0;i<=n;i++)C[i][0]=1; for(int i=1;i<=n;i++) for(int j=1;j<=i&&j<=4;j++) C[i][j]=C[i-1][j-1]+C[i-1][j]; for(int i=1;i<=n;i++) { int cnt=0; for(int j=1;j<=n;j++) { if(i==j)continue; a[++cnt]=atan2(p[j].y-p[i].y,p[j].x-p[i].x); if(a[cnt]<0)a[cnt]+=2*Pi; } sort(a+1,a+cnt+1); for(int j=1;j<=cnt;j++) a[j+cnt]=a[j]+2*Pi; for(int j=1,k=1;j<=cnt;j++) { while(a[k+1]-a[j]<Pi&&k<2*cnt)k++; tmp1-=C[k-j][2]; } tmp1+=C[n-1][3]; } tmp2=C[n][4]-tmp1; printf("%.6lf",(double)(tmp1+tmp2*2)/C[n][3]+3); } |
Comments | NOTHING