// Problem : Piece of Cake (NAIPC 2019) // Author : Darcy Best // Expected Result : AC // Complexity : O(n^2) // Compute the probability of a (directed) edge being on the // outside of the convex polygon and add the signed area below it. // (Using shoelace formula) // Compute the probabilities in a sweeping fashion. #include #include #include #include #include using namespace std; double area(const pair& p,const pair& q){ return p.first * q.second - p.second * q.first; } int main(){ int n, k; cin >> n >> k; vector > A(n); for(auto& x : A) cin >> x.first >> x.second; reverse(begin(A), end(A)); // I want counter-clockwise double ans = 0; for(int i=0;i= k-2;dist++,left--){ ans += prob * area(A[i],A[(i+dist)%n]); prob *= (left-(k-2)) / 1.0 / left; } } cout << fixed << setprecision(10) << ans/2 << endl; }