QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#731986#393. SignalingTheZone100 ✓173ms4524kbC++202.2kb2024-11-10 12:37:582024-11-10 12:38:02

Judging History

This is the latest submission verdict.

  • [2024-11-10 12:38:02]
  • Judged
  • Verdict: 100
  • Time: 173ms
  • Memory: 4524kb
  • [2024-11-10 12:37:58]
  • Submitted

answer

/*
#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/=2;
    int k=num-(n*(n-1)*(n-2)*(n-3)/12);
    num=(num-3*k)/2;
    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();
}

詳細信息


Pretests


Final Tests

Test #1:

score: 10
Accepted
time: 1ms
memory: 4372kb

input:

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

output:

5.9166666667

result:

ok found '5.91667', expected '5.91667', error '0.00000'

Test #2:

score: 10
Accepted
time: 1ms
memory: 4420kb

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:

10.3833333333

result:

ok found '10.38333', expected '10.38333', error '0.00000'

Test #3:

score: 10
Accepted
time: 1ms
memory: 4512kb

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:

23.3177551020

result:

ok found '23.31776', expected '23.31775', error '0.00000'

Test #4:

score: 10
Accepted
time: 1ms
memory: 4440kb

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:

44.2391898578

result:

ok found '44.23919', expected '44.23919', error '0.00000'

Test #5:

score: 10
Accepted
time: 3ms
memory: 4504kb

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:

86.1282945028

result:

ok found '86.12829', expected '86.12829', error '0.00000'

Test #6:

score: 10
Accepted
time: 15ms
memory: 4456kb

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:

193.1812085057

result:

ok found '193.18121', expected '193.18121', error '0.00000'

Test #7:

score: 10
Accepted
time: 18ms
memory: 4524kb

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:

213.6206740227

result:

ok found '213.62067', expected '213.62067', error '0.00000'

Test #8:

score: 10
Accepted
time: 75ms
memory: 4472kb

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:

424.1060140581

result:

ok found '424.10601', expected '424.10601', error '0.00000'

Test #9:

score: 10
Accepted
time: 173ms
memory: 4428kb

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:

636.5350248060

result:

ok found '636.53502', expected '636.53503', error '0.00000'

Test #10:

score: 10
Accepted
time: 169ms
memory: 4424kb

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:

637.3585487272

result:

ok found '637.35855', expected '637.35855', error '0.00000'