QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#413769#3001. Piece of Cakeucup-team1716#AC ✓80ms101948kbC++202.1kb2024-05-18 04:14:502024-05-18 04:14:50

Judging History

你现在查看的是最新测评结果

  • [2024-05-18 04:14:50]
  • 评测
  • 测评结果:AC
  • 用时:80ms
  • 内存:101948kb
  • [2024-05-18 04:14:50]
  • 提交

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'