QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#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';
}
詳細信息
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'