传送门 我们发现凸四边形贡献为2，凹四边形贡献为1 而且四边形总个数=C（n,4） 所以我们只要知道凹四边形的个数就可以了 我们枚举在凹四边形中内角大于180的点 然后我们将其他点按照极角序排序 枚举极角差刚刚不小于π的两条边 那么这两条边之间的点和其中一条边上的点不包含中间点。 由于按照极角排序，那么枚举的时间复杂度是O(n)。 设p为不包含中间点的三角形个数，那么以该点为中间点的凹四边形个数为C(n-1,3)-p。 最后的期望即为(a+2*b)/C(n,3)。
#include<cstdio> #include<iostream> #include<cstdlib> #include<cmath> #include<cstring> #include<algorithm> #define N 1505 #define pi 3.1415926535898 #define ll long long using namespace std; struct point{double x,y;}a[N]; double ang[N*2]; ll tu,ao,tot; int top,n,t; ll C(ll n,ll m){ if (m==2) return n*(n-1)/2; if (m==3) return n*(n-1)*(n-2)/6; return n*(n-1)*(n-2)*(n-3)/24; } void calc(int x){ top=0; for (int i=1;i<=n;i++) if (i!=x) ang[++top]=atan2(a[i].y-a[x].y,a[i].x-a[x].x); sort(ang+1,ang+top+1); tot=0; t=top; for (int i=1;i<=t;i++) ang[++top]=ang[i]+2*pi; int p=1; for (int i=1;i<=t;i++){ p=max(p,i+1); while (p<=top&&ang[p]<ang[i]+pi) p++; if (p-i-1>=2) tot+=C(p-i-1,2); } ao+=C(n-1,3)-tot; } int main(){ scanf("%d",&n); if (n<=3){printf("0"); return 0;} for (int i=1;i<=n;i++) scanf("%lf%lf",&a[i].x,&a[i].y); for (int i=1;i<=n;i++) calc(i); tu=C(n,4)-ao; printf("%lf",(double)(ao+tu*2)/C(n,3)+3); }