QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#56095 | #3001. Piece of Cake | YaoBIG# | AC ✓ | 84ms | 101060kb | C++ | 1.8kb | 2022-10-16 22:44:45 | 2022-10-16 22:44:48 |
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 = long double;
using P = Point<T>;
const int maxn = 2500;
vector<vector<T>> binom(maxn + 1, vector<T>(maxn + 1));
rep(i, 0, maxn) {
binom[i][0] = 1;
rep(j, 1, i) binom[i][j] = binom[i - 1][j - 1] + binom[i - 1][j];
}
debug(binom[maxn - 1][maxn / 2] / binom[maxn - 1][maxn / 2]);
int n, k; cin >> n >> k;
vector<P> as(n);
for (auto &[x, y]: as) cin >> x >> y;
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", (double) ans);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 16ms
memory: 100924kb
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: 81ms
memory: 101048kb
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.7145370705
result:
ok found '47.7145371', expected '47.7145371', error '0.0000000'
Test #3:
score: 0
Accepted
time: 67ms
memory: 101056kb
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:
267.9489554203
result:
ok found '267.9489554', expected '267.9489554', error '0.0000000'
Test #4:
score: 0
Accepted
time: 20ms
memory: 101056kb
input:
342 171 -9.998818 0.153747 -9.997917 0.202726 -9.997663 0.216208 -9.986909 0.482051 -9.977066 0.669980 -9.960055 0.892895 -9.943677 1.059735 -9.924803 1.223737 -9.922265 1.244011 -9.881584 1.527686 -9.871340 1.595884 -9.813970 1.916653 -9.787551 2.050325 -9.745125 2.243053 -9.683458 2.495799 -9.6678...
output:
266.6441933828
result:
ok found '266.6441934', expected '266.6441934', error '0.0000000'
Test #5:
score: 0
Accepted
time: 15ms
memory: 101060kb
input:
87 86 7.934712 5.851277 7.957370 5.901363 7.984885 5.912160 8.057904 5.888196 8.090706 5.871558 8.192155 5.734764 8.214245 5.702976 8.241768 5.663321 8.314438 5.556037 8.394960 5.433442 8.425523 5.386110 8.474268 5.308844 8.497539 5.271774 8.565648 5.160298 8.580590 5.135443 8.621362 5.066710 8.6895...
output:
3.2268546365
result:
ok found '3.2268546', expected '3.2268546', error '0.0000000'
Test #6:
score: 0
Accepted
time: 84ms
memory: 101056kb
input:
2496 2471 -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.99...
output:
314.1572713142
result:
ok found '314.1572713', expected '314.1572713', error '0.0000000'
Test #7:
score: 0
Accepted
time: 74ms
memory: 100924kb
input:
2379 1903 0.001241 9.999987 0.003330 9.999997 0.007027 9.999997 0.015799 9.999987 0.018521 9.999982 0.034934 9.999938 0.040716 9.999917 0.046881 9.999888 0.053865 9.999854 0.055231 9.999847 0.061980 9.999806 0.069431 9.999758 0.077677 9.999698 0.080054 9.999679 0.094173 9.999552 0.100783 9.999492 0....
output:
28.5359095707
result:
ok found '28.5359096', expected '28.5359096', error '0.0000000'