QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#413769 | #3001. Piece of Cake | ucup-team1716# | AC ✓ | 80ms | 101948kb | C++20 | 2.1kb | 2024-05-18 04:14:50 | 2024-05-18 04:14:50 |
Judging History
answer
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define double long double
using namespace std;
vector<vector<double>> choose(2501, vector<double>(2501, 0));
double find_area(double x1, double y1, double x2, double y2, double x3, double y3)
{
return abs(x1*y2+x2*y3+x3*y1-x2*y1-x3*y2-x1*y3) / 2;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cout << fixed << setprecision(12);
for(int i=0; i<=2500; i++)
{
for(int j=0; j<=i; j++)
{
if(j==0) choose[i][j] = 1;
else choose[i][j] = choose[i][j-1] / j * (i - j + 1);
}
}
int n, k;
cin >> n >> k;
vector<double> x(n), y(n);
for(int i=0; i<n; i++) cin >> x[i] >> y[i];
double ans1 = 0, S1 = 0, ans2 = 0, S2 = 0, ans3 = 0, S3 = 0;
for(int i=1; i<n; i++)
{
for(int j=i+1; j<n; j++)
{
double A = find_area(x[0], y[0], x[i], y[i], x[j], y[j]);
if(n-j+i-2>=k-3)
{
ans1 += A * choose[n-j+i-2][k-3];
S1 += choose[n-j+i-2][k-3];
}
if(n-j+i-2>=k-2)
{
ans2 += A * choose[n-j+i-2][k-2];
S2 += choose[n-j+i-2][k-2];
}
if(j-i-1>=k-2)
{
ans3 += A * choose[j-i-1][k-2];
S3 += choose[j-i-1][k-2];
}
}
}
//cout << ans1 << " " << ans2 << " " << ans3 << "\n";
//cout << S1 << " " << S2 << " " << S3 << "\n";
//assert(S2 / (k + 1) == S3);
//double p1 = ans1 * (k - 2) / S1, p2 = ans2 * (k - 1) / S2 - ans3 / S3;
//cout << p1 << " " << p2 << "\n";
cout << (ans1 + ans2 - ans3) / (S1 / (k - 2) + S3) << "\n";
/*for(int i=0; i<n; i++)
{
for(int j=i+1; j<n; j++)
{
for(int k=j+1; k<n; k++)
{
cout << i << " " << j << " " << k << " = " << find_area(x[i], y[i], x[j], y[j], x[k], y[k]) << "\n";
}
}
}*/
}
/*
5 4
0 4
4 2
4 1
3 -1
-2 4
*/
详细
Test #1:
score: 100
Accepted
time: 35ms
memory: 101700kb
input:
3 3 -5.236334 -8.519438 -9.987847 -0.492878 -9.994555 0.329962
output:
1.927946396220
result:
ok found '1.9279464', expected '1.9279464', error '0.0000000'
Test #2:
score: 0
Accepted
time: 80ms
memory: 101816kb
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.714537070548
result:
ok found '47.7145371', expected '47.7145371', error '0.0000000'
Test #3:
score: 0
Accepted
time: 52ms
memory: 101948kb
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.948955420305
result:
ok found '267.9489554', expected '267.9489554', error '0.0000000'
Test #4:
score: 0
Accepted
time: 27ms
memory: 101736kb
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.644193382799
result:
ok found '266.6441934', expected '266.6441934', error '0.0000000'
Test #5:
score: 0
Accepted
time: 35ms
memory: 101636kb
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.226854636528
result:
ok found '3.2268546', expected '3.2268546', error '0.0000000'
Test #6:
score: 0
Accepted
time: 35ms
memory: 101884kb
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.157271314212
result:
ok found '314.1572713', expected '314.1572713', error '0.0000000'
Test #7:
score: 0
Accepted
time: 44ms
memory: 101812kb
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.535909570667
result:
ok found '28.5359096', expected '28.5359096', error '0.0000000'