QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#863783#3001. Piece of CakeisWFnoya#AC ✓32ms131076kbC++262.5kb2025-01-19 22:20:282025-01-19 22:20:35

Judging History

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

  • [2025-01-19 22:20:35]
  • 评测
  • 测评结果:AC
  • 用时:32ms
  • 内存:131076kb
  • [2025-01-19 22:20:28]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
const int N=1919810;
#define double long double
typedef long long ll;
typedef pair<ll,ll> PII;
int n,m,k;
// int a[N],b[N];
double a[N],b[N];
char s[N];
double C[3000][3000];
double pw[N];

bool check(double K,double B,double x,double y){
    if(y>K*x+B) return true;
    return false;
}

void __(){
    // cin>>n>>m;
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>a[i]>>b[i];
    for(int i=1;i<=n*2;i++){
        a[i+n]=a[i];
        b[i+n]=b[i];
        // a[i+n]=a[i];
        // b[i+n]=b[i];
    }
    
    double ans=0;
    for(int i=1;i<=n;i++){
        for(int j=i+1;j<=n;j++){
            if(a[i]==a[j]) continue;
            double K=(b[j]-b[i])/(a[j]-a[i]);
            double B=b[i]-a[i]*K;
            double res=(b[i]+b[j])*fabs(a[i]-a[j])/2;
            // cout<<"--"<<res<<" ";
            double rres=(C[j-i-1][m-2]-C[n-(j-i+1)][m-2])/C[n][m];
            rres*=res;
            
            // if(j==i+2){
                // cout<<j-i-1<<" "<<m-2<<" "<<n-(j-i+1)<<" "<<C[j-i-1][m-2]/C[n][m]<<" "<<C[n-(j-i+1)][m-2]/C[n][m]<<endl;
                // cout<<rres<<endl;
            // }
            // if(j==i+1){
                bool flag=0;
                if(j==i+n-1){
                    if(check(K,B,a[i+1],b[i+1])){
                    // double rres=
                    ans-=rres;
                }else{
                    // double rres=(val[j-i-1][m-2]-val[n-(j-i+1)][m-2])*res;
                    ans+=rres;
                }
                }else
                if(check(K,B,a[j+1],b[j+1])){
                    // double rres=
                    ans+=rres;
                }else{
                    // double rres=(val[j-i-1][m-2]-val[n-(j-i+1)][m-2])*res;
                    ans-=rres;
                }
            // }
            // cout<<i<<" "<<j<<" "<<rres<<" "<<ans<<endl;
        }
    }
    // printf("%.20f\n",ans);
    cout << fixed << setprecision(20) << ans<< '\n' ;
}


int main(){
    
    
    for(int i=0;i<=2550;i++){
        C[i][0]=1;
    }
    for(int i=1;i<=2550;i++){
        for(int j=1;j<=i;j++){
            C[i][j]=(C[i-1][j]+C[i-1][j-1]);
        }
    }
    pw[0]=1;
    for(int i=1;i<=2550;i++) pw[i]=pw[i-1]*2;
    // val[0][0]=0;
    // for(int i=0;i<=10;i++){
    //     for(int j=0;j<=10;j++) cout<<val[i][j]<<" ";
    //     cout<<endl;
    // }
    int _=1;
    // cin>>_;
    while(_--){
        __();
    }
}

詳細信息

Test #1:

score: 100
Accepted
time: 9ms
memory: 128896kb

input:

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

output:

1.92794639622000000276

result:

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

Test #2:

score: 0
Accepted
time: 31ms
memory: 131072kb

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

result:

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

Test #3:

score: 0
Accepted
time: 27ms
memory: 131072kb

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

result:

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

Test #4:

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

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

result:

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

Test #5:

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

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

result:

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

Test #6:

score: 0
Accepted
time: 32ms
memory: 131076kb

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

result:

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

Test #7:

score: 0
Accepted
time: 30ms
memory: 129028kb

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

result:

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