QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#407091#393. Signalingbachbeo20070 173ms4452kbC++202.7kb2024-05-07 22:44:412024-05-07 22:44:42

Judging History

This is the latest submission verdict.

  • [2024-05-07 22:44:42]
  • Judged
  • Verdict: 0
  • Time: 173ms
  • Memory: 4452kb
  • [2024-05-07 22:44:41]
  • Submitted

answer

// Judges with GCC >= 12 only needs Ofast
// #pragma GCC optimize("O3,no-stack-protector,fast-math,unroll-loops,tree-vectorize")
// MLE optimization
// #pragma GCC optimize("conserve-stack")
// Old judges
// #pragma GCC target("sse4.2,popcnt,lzcnt,abm,mmx,fma,bmi,bmi2")
// New judges. Test with assert(__builtin_cpu_supports("avx2"));
// #pragma GCC target("avx2,popcnt,lzcnt,abm,bmi,bmi2,fma,tune=native")
// Atcoder
// #pragma GCC target("avx2,popcnt,lzcnt,abm,bmi,bmi2,fma")
/*
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
- insert(x),erase(x)
- find_by_order(k): return iterator to the k-th smallest element
- order_of_key(x): the number of elements that are strictly smaller
*/

#include<bits/stdc++.h>
using namespace std;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
uniform_real_distribution<> pp(0.0,1.0);
#define int long long
#define ld long double
#define pii pair<int,int>
#define piii pair<int,pii>
#define mpp make_pair
#define fi first
#define se second
const int inf=1e18;
const int mod=998244353;
const int maxn=3005;
const int bl=650;
const int maxs=655;
const int maxm=200005;
const int maxq=1000005;
const int maxl=25;
const int maxa=1000000;
const int root=3;
int power(int a,int n){
    int res=1;
    while(n){
        if(n&1) res=res*a%mod;
        a=a*a%mod;n>>=1;
    }
    return res;
}
const int iroot=power(3,mod-2);
const int base=131;

double PI = acos(-1.0);

struct vec{
    int x=0,y=0;
    double d;
    vec(int x=0,int y=0):x(x),y(y){
        d=atan2(y,x);
    }
    bool operator<(vec a){
        return d<a.d;
    }
}P[2*maxn];

int n,X[maxn],Y[maxn];
int total=0;

void solve(){
    cin >> n;
    for(int i=1;i<=n;i++) cin >> X[i] >> Y[i];
    int num=0;
    for(int t=1;t<=n;t++){
        for(int i=1;i<t;i++) P[i]=vec(X[i]-X[t],Y[i]-Y[t]);
        for(int i=t+1;i<=n;i++) P[i-1]=vec(X[i]-X[t],Y[i]-Y[t]);
        sort(P+1,P+n);
        int B=0;
        for(int i=1;i<n;i++){
            P[i+n-1]=P[i];
            P[i+n-1].d+=2*PI;
        }
        for(int i=1,j=1;i<n;i++){
            while(P[i].d+PI>P[j].d) B++,j++;
            num+=(B-1)*(n-1-B);B--;
        }
    }
    num/=4;
    int k=n*(n-1)*(n-2)*(n-3)/24-num;
    int cnt=n*(n-1)*(n-2)/6;
    total+=num*2+k;
    double ans=3+(double)total/cnt;
    cout << setprecision(10) << fixed << ans << '\n';
}

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);cout.tie(NULL);
    int test=1;//cin >> test;
    while(test--) solve();
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 1ms
memory: 4344kb

input:

10
-50 46
12 -45
-75 -9
63 -90
-55 58
34 -93
12 -56
-39 -92
-94 2
-97 56

output:

6.7916666667

result:

wrong answer 1st numbers differ - expected: '5.91667', found: '6.79167', error = '0.14789'

Test #2:

score: 0
Wrong Answer
time: 1ms
memory: 4404kb

input:

20
-92 -19
54 50
-73 8
31 99
-87 77
100 -23
27 71
70 47
-66 -61
-95 51
-69 -35
-72 22
-77 -54
-68 53
50 -32
-43 -42
3 59
-95 3
-7 -2
-43 -64

output:

12.0578947368

result:

wrong answer 1st numbers differ - expected: '10.38333', found: '12.05789', error = '0.16127'

Test #3:

score: 0
Wrong Answer
time: 1ms
memory: 4384kb

input:

50
-453 9273
8635 5374
7799 -7270
4790 5371
-4527 7088
-5703 116
1861 413
4233 -8269
-806 -6547
2147 -6368
6555 -7298
56 -2857
2201 7138
938 7735
-5991 3010
-2957 382
-8048 2456
449 -9863
-9972 8117
558 7923
-9198 -9065
-8252 5549
-7689 939
-3073 -9730
5708 -8504
-3763 -9209
7681 2139
5616 -4776
280...

output:

28.0911224490

result:

wrong answer 1st numbers differ - expected: '23.31775', found: '28.09112', error = '0.20471'

Test #4:

score: 0
Wrong Answer
time: 1ms
memory: 4444kb

input:

100
-2141 -4880
-9922 -5732
-1447 6911
-1075 -6956
-6494 -3573
8708 6799
4213 2423
6020 -1331
8680 4477
-8039 -2826
-7634 -528
-2889 -9898
4520 -6714
-2444 -4444
1162 1172
-2956 -6434
-8580 4504
-4828 837
7455 6831
-3319 2977
6809 -6073
7342 4840
6805 -1347
6238 6681
-1140 7819
6874 3130
-1002 -9025...

output:

55.1304019790

result:

wrong answer 1st numbers differ - expected: '44.23919', found: '55.13040', error = '0.24619'

Test #5:

score: 0
Wrong Answer
time: 3ms
memory: 4360kb

input:

200
-1122 14370
-42358 19597
-8142 -62821
-96727 50998
-39983 -1255
-9889 -32277
-76715 -26038
56558 30000
40878 -16623
-48090 -48731
15995 -5641
75446 -54677
63957 10714
-73685 58774
-51402 -9966
43245 13215
64833 62221
-33150 -97182
-57948 -30006
-39542 -59193
75510 70480
54803 6772
-20806 -42135
...

output:

109.1858527486

result:

wrong answer 1st numbers differ - expected: '86.12829', found: '109.18585', error = '0.26771'

Test #6:

score: 0
Wrong Answer
time: 15ms
memory: 4164kb

input:

450
311476 420680
-179437 -453868
692958 -289805
882929 -536362
-635778 -76866
-452292 737474
-319376 -97126
-436325 -624165
-830541 -235691
-32100 -25859
269774 -319553
-952967 -665867
-759030 -379696
-799622 531046
162770 929102
959448 -820442
-696548 250017
315619 869226
-950422 483601
-238243 92...

output:

243.1593957472

result:

wrong answer 1st numbers differ - expected: '193.18121', found: '243.15940', error = '0.25871'

Test #7:

score: 0
Wrong Answer
time: 19ms
memory: 4448kb

input:

500
901932 -831127
177611 -452336
-81615 -260260
-868737 915377
-805269 -567574
-621357 -983383
-478831 -753449
-146546 929599
-705635 256170
55217 -697919
-708568 -316283
720771 -686336
568982 851708
569161 638609
-641368 -750581
-247391 301211
-342708 673355
393219 -184972
-676469 154890
-559945 8...

output:

270.4396629886

result:

wrong answer 1st numbers differ - expected: '213.62067', found: '270.43966', error = '0.26598'

Test #8:

score: 0
Wrong Answer
time: 75ms
memory: 4452kb

input:

1000
618441 536922
-670652 756937
-951203 -88976
-96750 102377
-49403 267613
-202790 492478
328782 -572207
-401320 -225835
-533681 -451907
298806 -554354
-933347 -292249
-396171 -911579
-211258 458880
60941 -128449
-856581 -816717
-782661 221946
219834 -400346
531242 -745577
-789282 -735078
253598 5...

output:

540.1969929709

result:

wrong answer 1st numbers differ - expected: '424.10601', found: '540.19699', error = '0.27373'

Test #9:

score: 0
Wrong Answer
time: 169ms
memory: 4392kb

input:

1500
-466267 -545644
842097 -947922
699094 -376679
708277 42478
712256 813305
-629139 377724
795013 -265652
885435 362587
105505 -151452
419402 618775
-824399 431939
936446 382165
-227899 -244470
476667 778569
-349480 729226
-248801 -328251
-829799 -147620
270009 -822539
-760492 814759
-278341 -5627...

output:

808.9824875970

result:

wrong answer 1st numbers differ - expected: '636.53503', found: '808.98249', error = '0.27092'

Test #10:

score: 0
Wrong Answer
time: 173ms
memory: 4252kb

input:

1500
372361 -892254
674948 369064
663890 427706
-962493 -748469
-296124 -837649
366715 89587
414772 -877335
-788861 594332
-306600 -691
-443204 -140585
325874 -187797
-549930 -649347
-689284 -598867
-174278 921052
-691067 551110
-491282 -305052
439793 -153742
858640 165072
141049 845958
-974583 3462...

output:

808.5707256355

result:

wrong answer 1st numbers differ - expected: '637.35855', found: '808.57073', error = '0.26863'