// Problem : Piece of Cake (NAIPC 2019) // Author : Darcy Best // Expected Result : AC -- or possibly TLE // Complexity : O(n^2 log n) [log(n) just for safety, see below] // 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. // I'm computing all the values, then adding them together in // a "safe-ish" way by adding similar magnitude numbers together #include #include #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 priority_queue, greater > pq; for(int i=0;i= k-2;dist++,left--){ pq.emplace(prob * area(A[i],A[(i+dist)%n])); prob *= (left-(k-2)) / 1.0 / left; } } while((int)pq.size() > 1){ double x = pq.top(); pq.pop(); while(pq.size() && pq.top() > x){ x += pq.top(); pq.pop(); } if(pq.size()){ x += pq.top(); pq.pop(); } pq.push(x); } cout << fixed << setprecision(10) << pq.top()/2 << endl; }