QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#109466#3001. Piece of CakeidontreallyknowAC ✓48ms3860kbC++171.6kb2023-05-29 08:56:372023-05-29 08:56:41

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-05-29 08:56:41]
  • 评测
  • 测评结果:AC
  • 用时:48ms
  • 内存:3860kb
  • [2023-05-29 08:56:37]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
using ld = long double;
ld read() {
    string s;
    cin >> s;
    return stold(s);
}
ld pt[2505][2], mul[2505];
bool num[2505], den[2505];
int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n,k;
    cin >> n >> k;
    auto prob = [&](int i) {
        for (int j = 0; j < k-2; j++) {
            num[n-i-2-j] = true;
            den[n-j] = true;
        }
        vector<int> remn, remd;
        for (int j = 0; j < 2505; j++) {
            if (num[j] == den[j]) continue;
            if (num[j]) remn.push_back(j);
            if (den[j]) remd.push_back(j);
        }
        ld ret = k*(k-1)/2;
        assert(remn.size() == remd.size());
        while (remn.size()) {
            ret *= remn.back();
            ret /= remd.back();
            remn.pop_back();
            remd.pop_back();
        }
        for (int j = 0; j < k-2; j++) {
            num[n-i-2-j] = false;
            den[n-j] = false;
        }
        ret *= 2;
        ret /= ((n-k+2)*(n-k+1));
        return ret;
    };
    for (int i = 0; i < n; i++) {
        pt[i][0] = read();
        pt[i][1] = read();
    }
    vector<int> ind(n);
    iota(ind.begin(),ind.end(),0);
    reverse(ind.begin(),ind.end());
    ld tot = 0;
    for (int i = 0; i <= n-k; i++) {
        ld pos = 0, neg = 0;
        for (int j = 0; j < n; j++) {
            int l = (j+i+1)%n;
            pos += pt[ind[j]][0]*pt[ind[l]][1];
            neg += pt[ind[j]][1]*pt[ind[l]][0];
        }
        ld ret = prob(i)*(pos-neg);
        tot += ret;
    }
    cout << setprecision(20) << tot/2 << '\n';
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 2ms
memory: 3584kb

input:

3 3
-5.236334 -8.519438
-9.987847 -0.492878
-9.994555 0.329962

output:

1.9279463962200000006

result:

ok found '1.9279464', expected '1.9279464', error '0.0000000'

Test #2:

score: 0
Accepted
time: 48ms
memory: 3844kb

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.714537070548314633

result:

ok found '47.7145371', expected '47.7145371', error '0.0000000'

Test #3:

score: 0
Accepted
time: 21ms
memory: 3624kb

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.94895542030523991

result:

ok found '267.9489554', expected '267.9489554', error '0.0000000'

Test #4:

score: 0
Accepted
time: 3ms
memory: 3608kb

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.64419338279892221

result:

ok found '266.6441934', expected '266.6441934', error '0.0000000'

Test #5:

score: 0
Accepted
time: 2ms
memory: 3668kb

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.2268546365279599821

result:

ok found '3.2268546', expected '3.2268546', error '0.0000000'

Test #6:

score: 0
Accepted
time: 3ms
memory: 3860kb

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.15727131421242188

result:

ok found '314.1572713', expected '314.1572713', error '0.0000000'

Test #7:

score: 0
Accepted
time: 9ms
memory: 3860kb

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.535909570667295729

result:

ok found '28.5359096', expected '28.5359096', error '0.0000000'