题解与代码 - Piece of Cake

Piece of Cake

题解

考虑计算 $n$ 边形之内， $k$ 边形之外的面积期望。

不妨钦定两个点作为一条边，接着只需要从两个点之间的点中选取 $k-2$ 个即可构成多边形，对答案的贡献即为另一边的多边形部分。

时间复杂度 $\Theta(n^2)$ 。注意使用 long double 以避免精度问题。

代码

// 2023.05.29

#include<bits/stdc++.h>
using namespace std;

long double C[2501][2501];
void initC(int N){
    C[0][0]=1;
    for(int i=1;i<=N;i++){
        C[i][0]=1;
        for(int j=1;j<=i;j++)
            C[i][j]=C[i-1][j]+C[i-1][j-1];
    }
}

int n,k;
struct Point{
    long double x,y;
}a[2501];

long double calc(Point A,Point B){
    return (long double)A.x*B.y-(long double)A.y*B.x;
}

int main(){
    initC(2500);
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++)
        scanf("%Lf%Lf",&a[i].x,&a[i].y);
    long double sum=0;
    for(int i=1;i<=n;i++)
        for(int t=k-1;t<n;t++){
            int j=i+t; if(j>n)j-=n;
            sum+=calc(a[i],a[j])*C[t-1][k-2]/C[n][k];
        }
    printf("%.7Lf\n",sum/2);
    return 0;
}