Piece of Cake Kattis - pieceofcake （几何面积+概率）

题目

https://cn.vjudge.net/problem/Kattis-pieceofcake

题意

给你n个点，选k个点，面积期望是多少

思路

枚举两个点形成凸包的概率，计算他们对期望的贡献

凸包面积 = 相邻的两点的叉积和

这个点形成凸包的个数为这C（k-2，这两个点中间的点）

贡献 它在凸包的面积*选中的概率

long long double减下误差

求组合数没取模是因为double是科学计数法，不会爆，只会产生误差。

代码

#include <bits/stdc++.h>using namespace std;
typedef long long ll;
struct point
{long double x,y;
}a[2555];
long double C[2555][2555];
long double cross(point a,point b)
{return a.x*b.y - a.y*b.x;
}
int main()
{int n,k;scanf("%d%d",&n,&k);for(int i = 0;i < n;i++){scanf("%llf%llf",&a[i].x,&a[i].y);}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];}}long double res = 0;for(int i = 0;i < n;i++){for(int j = k-1;j < n;j++){int x = (i+j)%n;res += cross(a[i],a[x]) * C[j-1][k-2] / C[n][k];}}printf("%.10llf\n",res/2);return 0;
}