QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#395151 | #3001. Piece of Cake | ohiostatescarlet# | AC ✓ | 947ms | 4116kb | C++17 | 1.4kb | 2024-04-21 08:39:26 | 2024-04-21 08:39:27 |
Judging History
answer
#include "bits/stdc++.h"
using namespace std;
#define L long long;
#ifdef LOCAL
#define dbg(x) cerr << "[" << (#x) << " = " << (x) << "]\n";
#else
#define dbg(x)
#endif
// g++ -std=c++17 -O2 -DLOCAL -o a a.cpp
double cross(vector<double> a, vector<double> b) {
return a[0] * b[1] - a[1] * b[0];
}
double area(vector<vector<double>> arr) {
double ans = cross(arr.back(), arr[0]);
for (int i = 0; i + 1 < arr.size(); i++) {
ans += cross(arr[i], arr[i + 1]);
}
return fabs(ans) / 2;
}
int main() {
cin.tie(0)->sync_with_stdio(0);
int n, select; cin >> n >> select;
int k = n - select;
vector<double> comp(k + 1, 1);
if (comp.size() > 1) {
comp[1] = double(k) * (n - k - 1) * (n - k) / (double(n) * (n - 1) * (n - 2));
for (int y = 2; y < comp.size(); y++) {
comp[y] = comp[y - 1] / (n - y - 1) * (k - y + 1);
}
}
vector<vector<double>> p(n, vector<double>(2));
for (int i = 0; i < n; i++) {
cin >> p[i][0] >> p[i][1];
}
double total = area(p);
for (int start = 0; start < n; start++) {
double a = 0;
vector<vector<double>> points = {p[start], {0, 0}, {p[(start + 1) % n]}};
for (int y = 1; y < k + 1; y++) {
int end = start + y + 1;
points[1] = points[2];
points[2] = p[end % n];
a += area(points);
total -= a * comp[y];
}
}
cout << fixed << setprecision(10) << total << '\n';
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3764kb
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: 947ms
memory: 4116kb
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: 0
Accepted
time: 321ms
memory: 4060kb
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.9489554204
result:
ok found '267.9489554', expected '267.9489554', error '0.0000000'
Test #4:
score: 0
Accepted
time: 9ms
memory: 4100kb
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: 0ms
memory: 3924kb
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: 11ms
memory: 4096kb
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: 163ms
memory: 4036kb
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'