QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#56093 | #3001. Piece of Cake | YaoBIG# | WA | 56ms | 52104kb | C++ | 1.8kb | 2022-10-16 22:30:07 | 2022-10-16 22:30:10 |
Judging History
answer
#include "bits/stdc++.h"
#define rep(i, a, n) for (auto i = a; i <= (n); ++i)
#define revrep(i, a, n) for (auto i = n; i >= (a); --i)
#define all(a) a.begin(), a.end()
#define sz(a) (int)(a).size()
using namespace std;
template<class A> string to_string(A v) {
bool first = 1;
string res = "{";
for (const auto &x: v) {
if (!first) res += ", ";
first = 0;
res += to_string(x);
}
res += "}";
return res;
}
void debug_out() { cerr << endl; }
template<class Head, class... Tail> void debug_out(Head H, Tail... T) {
cerr << " " << to_string(H);
debug_out(T...);
}
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
using ll = long long;
using pii = pair<int, int>;
using vi = vector<int>;
using vvi = vector<vi>;
template<class T>
struct Point {
using P = Point;
T x, y;
P operator -(P b) const { return P{x - b.x, y - b.y}; }
T cross(P b) const { return x * b.y - y * b.x; }
};
int main() {
ios::sync_with_stdio(0); cin.tie(0);
using T = double;
using P = Point<T>;
int n, k; cin >> n >> k;
vector<P> as(n);
for (auto &[x, y]: as) cin >> x >> y;
vector<vector<T>> binom(n + 1, vector<T>(n + 1));
rep(i, 0, n) {
binom[i][0] = 1;
rep(j, 1, i) binom[i][j] = binom[i - 1][j - 1] + binom[i - 1][j];
}
// debug(binom[n][n / 2] / binom[n - 1][n / 2]);
T ans = 0;
rep(i, 0, n - 1) {
P a = as[i];
P b = as[(i + 1) % n];
ans += b.cross(a) / 2;
}
// debug(ans);
rep(i, 0, n - 1) {
P a = as[i];
T sum = 0;
rep(j, 1, n - 1) {
P b = as[(i + j - 1) % n];
P c = as[(i + j) % n];
int cnt = n - (j + 1);
if (n < k - 2) break;
sum += (c - a).cross(b - a) / 2;
ans -= binom[cnt][k - 2] / binom[n][k] * sum;
}
}
printf("%.10f\n", ans);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 3812kb
input:
3 3 -5.236334 -8.519438 -9.987847 -0.492878 -9.994555 0.329962
output:
1.9279463962
result:
ok found '1.9279464', expected '1.9279464', error '0.0000000'
Test #2:
score: 0
Accepted
time: 56ms
memory: 52104kb
input:
2496 3 -9.999961 0.028130 -9.999655 0.083151 -9.999641 0.084830 -9.999572 0.092537 -9.999474 0.102653 -9.999366 0.112678 -9.999329 0.115862 -9.998360 0.181104 -9.998033 0.198381 -9.997191 0.237035 -9.995264 0.307754 -9.993680 0.355494 -9.992454 0.388414 -9.992180 0.395407 -9.992030 0.399190 -9.99086...
output:
47.7145370706
result:
ok found '47.7145371', expected '47.7145371', error '0.0000000'
Test #3:
score: -100
Wrong Answer
time: 36ms
memory: 37880kb
input:
2099 1049 -9.999906 0.043015 -9.999734 0.072371 -9.999721 0.074260 -9.999602 0.089189 -9.999407 0.108349 -9.999328 0.115856 -9.998818 0.153747 -9.998136 0.193060 -9.997663 0.216208 -9.997463 0.225142 -9.996961 0.246480 -9.995978 0.282576 -9.995847 0.287087 -9.995567 0.296415 -9.994353 0.335674 -9.99...
output:
-nan
result:
wrong output format Expected double, but "-nan" found