QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#888160#9823. Mouse TrapisWFnoyaWA 38ms29752kbC++262.2kb2025-02-07 23:02:522025-02-07 23:02:52

Judging History

This is the latest submission verdict.

  • [2025-02-07 23:02:52]
  • Judged
  • Verdict: WA
  • Time: 38ms
  • Memory: 29752kb
  • [2025-02-07 23:02:52]
  • Submitted

answer

#include<bits/stdc++.h>
using namespace std;
const int N=1919810;
typedef long long ll;
typedef pair<ll,ll> PII;
ll n,m,k;
ll x[N],y[N];
double s[N],S[N];
double rs[N];
double sum[N],cnt[N];


int find(int l,int r,int X){
    int num=x[l];
    while(l<r){
        int mid=l+r+1>>1;
        if(x[mid]>=num) l=mid;
        else r=mid-1;
    }
    return l;
}

double query(int l,int r){
    double ans=s[r]-s[l-1];
    double res=S[r]-S[l-1];
    res*=(l-1)*2;
    ans-=res;
    return ans;
}

double query2(int l,int r){
    double ans=rs[l]-rs[r+1];
    double res=S[r]-S[l-1];
    res*=(n-r)*2;
    ans-=res;
    return ans;
}

void __(){
    scanf("%lld",&n);
    for(int i=1;i<=n;i++){
        scanf("%lld%lld",&x[i],&y[i]);
        x[i+n]=x[i];
        y[i+n]=y[i];
    }
    // reverse(x+1,x+1+n);
    // reverse(y+1,y+1+n);
    for(int i=1;i<=n*2;i++){
        S[i]=y[i];
        s[i]=y[i]*i*2;
        S[i]+=S[i-1];
        s[i]+=s[i-1];
        // cout<<s[i]<<" "<<S[i]<<endl;
    }
    for(int i=n*2;i>=1;i--){
        rs[i]=y[i]*(n+1-i)*2;
        rs[i]+=rs[i+1];
    }
    // for(int i=1;i<=n;i++)
    for(int i=1;i<=n;i++){
        int t=find(i,n+i-1,x[i]);
        int sz=t-i;
        // t-=i;
        // cout<<sz<<endl;
        ll val=(sz*(n-2)-sz*(sz-1));
        // cout<<val<<endl;
        cnt[i]-=val;
        sum[i]-=n*(S[t]-S[i]);
        sum[i]+=query(i+1,t);

        sz=n-sz-1;
        // cout<<sz<<endl;
        val=(sz*(n-2)-sz*(sz-1));
        cnt[i]+=val;
        sum[i]+=n*(S[n+i-1]-S[t]);
        sum[i]-=query2(t+1,n+i-1);
        
        // cout<<n*(S[t]-S[i])<<" "<<n*(S[n]-S[t])<<" "<<query(i+1,t)<<" "<<query2(t+1,n)<<endl;
    }
    double fm=0;
    for(int i=1;i<=n;i++){
        fm+=(x[i]*y[i+1]-x[i+1]*y[i]);
    }
    
    double ans=0;
    for(int i=1;i<=n;i++){
        double res=x[i]*y[i];
        res*=cnt[i];
        ans+=res;
        ans+=sum[i]*x[i];
        // cout<<res<<" "<<sum[i]*x[i]<<endl;
        // cout<<cnt[i]<<" "<<sum[i]<<endl;
        // cout<<ans<<endl;
    }
    // cout<<ans<<endl;
    ans/=fm;
    printf("%.15f\n",-ans);
}


int main(){
    int _=1;
    // cin>>_;
    while(_--){
        __();
    }
}

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 8016kb

input:

4
0 0
1 0
1 1
0 1

output:

2.000000000000000

result:

ok found '2.00000', expected '2.00000', error '0.00000'

Test #2:

score: 0
Accepted
time: 0ms
memory: 8136kb

input:

5
0 0
1 0
2 1
1 2
0 2

output:

3.666666666666667

result:

ok found '3.66667', expected '3.66667', error '0.00000'

Test #3:

score: 0
Accepted
time: 0ms
memory: 8136kb

input:

3
-3141592 -2718281
-3141593 -2718281
-3141592 -2718282

output:

1.000000000000000

result:

ok found '1.00000', expected '1.00000', error '0.00000'

Test #4:

score: 0
Accepted
time: 0ms
memory: 8012kb

input:

4
-10000000 -10000000
10000000 -10000000
10000000 10000000
-10000000 10000000

output:

2.000000000000000

result:

ok found '2.00000', expected '2.00000', error '0.00000'

Test #5:

score: 0
Accepted
time: 0ms
memory: 7972kb

input:

6
-10000000 -10000000
0 -10000000
10000000 0
10000000 10000000
0 10000000
-10000000 0

output:

6.000000000000000

result:

ok found '6.00000', expected '6.00000', error '0.00000'

Test #6:

score: 0
Accepted
time: 0ms
memory: 8012kb

input:

80
-56 -1
-55 -6
-54 -10
-53 -13
-51 -18
-50 -20
-47 -25
-45 -28
-42 -32
-38 -37
-37 -38
-32 -42
-28 -45
-25 -47
-20 -50
-18 -51
-13 -53
-10 -54
-6 -55
-1 -56
0 -56
5 -55
9 -54
12 -53
17 -51
19 -50
24 -47
27 -45
31 -42
36 -38
37 -37
41 -32
44 -28
46 -25
49 -20
50 -18
52 -13
53 -10
54 -6
55 -1
55 0
5...

output:

13022.364675557548253

result:

ok found '13022.36468', expected '13022.36468', error '0.00000'

Test #7:

score: 0
Accepted
time: 0ms
memory: 8396kb

input:

4336
-22883 -1
-22882 -43
-22881 -84
-22880 -124
-22879 -163
-22878 -201
-22877 -238
-22876 -274
-22875 -309
-22874 -343
-22873 -376
-22872 -408
-22871 -439
-22870 -469
-22869 -498
-22868 -526
-22867 -553
-22866 -579
-22865 -604
-22864 -628
-22863 -651
-22862 -673
-22861 -694
-22859 -735
-22858 -755...

output:

2071959690.152333021163940

result:

ok found '2071959690.15233', expected '2071959690.15233', error '0.00000'

Test #8:

score: -100
Wrong Answer
time: 38ms
memory: 29752kb

input:

199344
-7134251 -1
-7134250 -287
-7134249 -572
-7134248 -856
-7134247 -1139
-7134246 -1421
-7134245 -1702
-7134244 -1982
-7134243 -2261
-7134242 -2539
-7134241 -2816
-7134240 -3092
-7134239 -3367
-7134238 -3641
-7134237 -3914
-7134236 -4186
-7134235 -4457
-7134234 -4727
-7134233 -4996
-7134232 -5264...

output:

114443304684019.718750000000000

result:

wrong answer 1st numbers differ - expected: '201338821149252.00000', found: '114443304684019.71875', error = '0.43159'