QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#805469#9869. Horizon ScanningLittleXi#AC ✓51ms7272kbC++171.4kb2024-12-08 16:50:062024-12-08 16:50:06

Judging History

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

  • [2024-12-08 16:50:06]
  • 评测
  • 测评结果:AC
  • 用时:51ms
  • 内存:7272kb
  • [2024-12-08 16:50:06]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define For(i,a,b) for(int i=(a);i<=(b);i++)
#define Rof(i,a,b) for(int i=(a);i>=(b);i--)
#define db long double
#define ll long long
#define wln putchar('\n')
const int N=200005;
const db eps=1e-10,pi=acos(-1);
struct vec2{int x,y;}p[N*2];
ll operator *(vec2 a,vec2 b){return 1ll*a.x*b.x+1ll*a.y*b.y;}
ll operator /(vec2 a,vec2 b){return 1ll*a.x*b.y-1ll*a.y*b.x;}
db abs(vec2 a){return sqrt((db)(1ll*a.x*a.x+1ll*a.y*a.y));}
int xx(vec2 a)
{
    if(a.x>0&&a.y>=0)return 1;
    if(a.x<=0&&a.y>0)return 2;
    if(a.x<0&&a.y<=0)return 3;
    if(a.x>=0&&a.y<0)return 4;
    return 0;
}
bool cmp(vec2 a,vec2 b)
{
    int xa=xx(a),xb=xx(b);
    if(xa!=xb)return xa<xb;
    return a/b>0;
}
db angle_between(vec2 a,vec2 b)
{
    db t1=atan2(a.y,a.x),t2=atan2(b.y,b.x);
    db t=t2-t1;
    if(t<-eps)t+=2*pi;
    return t;
}
int n,k;
void Main()
{
    scanf("%d%d",&n,&k);
    For(i,1,n)scanf("%d%d",&p[i].x,&p[i].y);
    if(k==n){printf("%.7Lf\n",2*pi); return;}
    sort(p+1,p+n+1,cmp);
    copy(p+1,p+n+1,p+n+1);
    // For(i,1,n)printf("(%d,%d)",p[i].x,p[i].y); wln;
    db ans=0;
    For(i,1,n)
    {
        db t=angle_between(p[i],p[i+k]);
        if(abs(t)<eps&&(i-1)%n>(i+k-1)%n)t+=2*pi;
        ans=max(ans,t);
    }
    printf("%.7Lf\n",ans);
}
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)Main();
}

这程序好像有点Bug,我给组数据试试?

详细

Test #1:

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

input:

5
1 1
0 1
8 2
1 0
1 1
0 1
-1 1
-1 0
-1 -1
0 -1
1 -1
4 2
-1 1
0 1
0 2
1 1
4 2
-1000000000 0
-998244353 1
998244353 1
1000000000 0
3 1
0 1
0 2
0 -1

output:

6.2831853
1.5707963
5.4977871
3.1415927
3.1415927

result:

ok 5 numbers

Test #2:

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

input:

10000
16 1
-10 -6
-5 -6
-4 9
-2 5
-2 10
1 -7
1 -5
1 6
3 1
4 -9
6 -10
6 -3
6 1
8 -5
8 -4
9 -4
17 4
-9 2
-8 -4
-8 -3
-8 -1
-6 -2
-6 -1
-6 8
-5 -8
-5 10
-4 8
-2 -8
4 -9
4 0
5 -3
8 -5
9 -2
10 10
10 6
-7 2
-4 6
-2 -7
-2 -1
-1 7
1 -9
1 8
3 -4
7 -4
9 -2
14 3
-9 10
-8 -10
-8 -8
-6 -7
-6 -5
-1 -7
-1 -2
0 -1
...

output:

1.6929915
2.5748634
4.6527583
2.7726331
5.7427658
4.8576990
3.4198923
2.8128000
6.2831853
6.2831853
5.1172808
6.1467827
3.8420890
2.3424967
3.4633432
6.2831853
5.9614348
3.3247035
5.2627749
5.6724593
1.6738779
1.1141909
2.4087776
6.2831853
5.3558901
3.7998606
4.1932429
4.0513458
4.5342960
4.3612351
...

result:

ok 10000 numbers

Test #3:

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

input:

10000
19 7
-10 -6
-10 5
-3 0
-2 -5
-1 1
-1 6
0 3
0 7
1 9
3 -3
3 3
3 8
4 -1
5 8
6 -3
7 -5
7 4
8 10
9 -5
15 15
-9 -1
-8 6
-7 9
-6 -3
-4 -9
-1 -3
-1 8
1 -8
1 -7
3 -2
3 1
6 -9
7 -10
7 0
10 -9
10 3
-7 -1
-6 -2
-6 10
-5 2
-4 2
-3 -7
-2 -9
1 -3
3 4
7 7
15 4
-8 -8
-8 8
-7 0
-7 10
-6 -7
-5 6
-1 -3
-1 0
1 -2
...

output:

3.9269908
6.2831853
3.3602616
2.6779450
3.7703889
1.7625845
3.8402525
5.4977871
2.0344439
1.8157750
4.3471875
6.1412883
5.1760366
5.4655403
5.7690392
4.3662530
5.9947557
4.8922425
4.1719695
5.6776406
5.9614348
3.5067941
4.5429759
5.3003916
4.4937200
3.1415927
6.2831853
6.2692002
4.6801421
5.4977871
...

result:

ok 10000 numbers

Test #4:

score: 0
Accepted
time: 29ms
memory: 4344kb

input:

10000
18 12
-10 -4
-10 7
-8 -10
-7 -4
-6 5
-6 7
-5 0
-2 -7
-1 2
-1 10
0 2
1 1
3 -2
5 3
5 5
6 -3
8 -3
9 -2
10 1
-10 -9
-7 -7
-5 2
-4 -7
-3 1
3 1
3 3
5 -4
9 2
9 6
11 2
-8 1
-8 6
-7 -2
-6 0
-5 0
-1 -9
2 -8
3 5
6 0
10 -2
10 6
20 9
-10 -6
-10 6
-9 -8
-7 5
-6 -4
-4 -8
-2 -10
-2 -3
-2 4
-1 1
2 -5
3 -2
5 -6...

output:

4.9097845
1.9756881
1.9868608
3.9269908
3.6977589
6.2831853
6.1412883
6.1938713
5.8053543
6.2528915
5.7288778
3.0900918
1.8925469
5.6341897
2.8966140
6.2831853
2.9147938
6.1476576
1.9513027
5.5643553
5.4977871
3.0981418
4.3906384
3.9094488
2.6415239
6.1588303
5.8782935
6.2831853
3.0648208
5.6840100
...

result:

ok 10000 numbers

Test #5:

score: 0
Accepted
time: 29ms
memory: 4252kb

input:

10000
19 7
-10 -1
-8 2
-7 -10
-6 6
-4 7
-3 -5
-3 1
-3 8
-2 4
-1 -7
0 -8
0 9
1 -10
2 1
2 3
3 5
6 -4
10 2
10 3
14 10
-8 2
-6 0
-5 -10
-5 10
-4 7
-3 -6
-2 -6
1 4
1 6
2 -1
3 -6
8 -4
9 -10
10 -1
12 8
-9 5
-7 2
-4 2
0 -2
0 5
1 6
3 2
4 9
5 5
7 -6
9 -9
9 2
19 12
-10 -10
-10 2
-9 -6
-8 2
-7 -5
-6 8
-4 1
-1 -...

output:

3.2393196
5.2757052
5.3003916
5.3871299
5.8883942
4.1173194
1.1383886
1.5152978
6.1476576
6.1588303
2.5748634
5.9401614
1.6085143
4.6099451
5.0711597
4.2345579
3.7905882
4.0376480
3.9160022
1.0636978
4.2809883
5.8572557
3.4078447
5.4210153
2.9562447
1.6704650
5.8698549
4.3567531
6.1180366
6.1801037
...

result:

ok 10000 numbers

Test #6:

score: 0
Accepted
time: 29ms
memory: 4252kb

input:

10000
11 10
-10 -1
-9 4
-9 10
-7 -7
-5 4
-4 -1
-2 -10
0 -7
0 5
3 3
3 5
12 12
-9 6
-9 8
-3 -2
-2 2
0 -4
1 0
2 -3
3 5
5 -2
7 -1
10 3
10 9
14 12
-10 0
-9 -3
-9 1
-9 10
-8 -1
-8 7
-6 -1
-1 -6
-1 2
1 -1
3 -7
4 9
9 -3
10 1
10 4
-9 -3
-7 -1
-6 -10
-3 -2
-3 7
2 -2
2 3
5 2
6 9
9 6
10 2
-9 -9
-9 6
-8 3
-5 -9
...

output:

6.1378753
6.2831853
6.1180366
3.2003485
2.6537562
6.2537820
3.6052403
3.5598170
1.5091462
5.9275494
6.2587999
2.6224465
4.3938333
5.4977871
4.2487414
5.4977871
4.6292477
3.5464844
6.0048856
1.1967519
2.8854413
6.2000441
1.9237867
5.6629358
5.7427658
4.5149934
3.7295953
5.0341395
1.6929915
4.8775377
...

result:

ok 10000 numbers

Test #7:

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

input:

10000
14 1
-100 13
-96 -31
-82 -92
-77 -98
-50 1
-14 -57
-14 -31
-11 64
-8 75
9 68
25 100
54 -36
59 13
93 31
19 19
-76 -39
-60 95
-51 18
-39 11
-21 -46
-6 -94
-5 83
-3 -34
-3 72
0 -55
3 79
14 17
23 -88
32 37
50 70
61 -5
62 -43
84 -100
97 -50
13 7
-99 -63
-68 -87
-24 62
-20 -18
-2 -66
7 -49
13 -21
15...

output:

1.2713094
6.2831853
5.2225147
6.0030657
3.9258721
5.5465290
3.2103149
3.0399300
4.2275318
3.0320197
2.1912152
3.0390081
4.3313272
6.2831853
5.1100023
2.9463140
5.1760366
5.6991836
2.0611799
6.2831853
2.2278898
6.1707749
6.2831853
6.2831853
6.2823400
2.7193340
6.2831853
6.2831853
2.3752817
6.1583378
...

result:

ok 10000 numbers

Test #8:

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

input:

100
1413 755
-30 -30
-30 -28
-30 -27
-30 -26
-30 -21
-30 -12
-30 -10
-30 -8
-30 -5
-30 -1
-30 2
-30 4
-30 7
-30 9
-30 17
-30 19
-30 20
-30 23
-30 24
-30 30
-29 -29
-29 -23
-29 -15
-29 0
-29 4
-29 5
-29 9
-29 10
-29 11
-29 12
-29 14
-29 16
-29 17
-29 22
-29 27
-29 28
-28 -28
-28 -25
-28 -23
-28 -22
-...

output:

3.5891126
2.9797552
0.2837941
2.0350277
4.8879811
1.0040671
4.7457100
5.3255963
4.3102750
5.6033837
1.5798051
4.3296455
5.5472221
1.4601391
1.5310446
2.8716749
2.6325790
3.1240506
0.6805212
5.4201656
4.7789571
2.4030352
4.2799812
4.6785037
4.0037627
3.7670777
4.5826864
1.3240223
5.6396842
1.8823432
...

result:

ok 100 numbers

Test #9:

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

input:

20
9045 8319
-1000 -986
-1000 -683
-1000 -430
-1000 -292
-1000 53
-1000 667
-999 -855
-999 -350
-999 -174
-999 -51
-999 -43
-999 235
-999 465
-999 530
-998 -997
-998 -311
-998 21
-998 44
-998 182
-997 -313
-997 -195
-997 -13
-997 412
-997 425
-996 -542
-996 -348
-996 -126
-996 -59
-996 -40
-996 84
-...

output:

5.9115110
3.7438685
2.5384829
2.1599674
4.2950377
4.7716745
4.6824078
5.0789844
1.6008018
3.3404025
3.3687925
2.1130160
4.8553994
4.3240011
0.1078536
0.1798211
5.3766548
4.4495660
4.3944017
2.9381849

result:

ok 20 numbers

Test #10:

score: 0
Accepted
time: 36ms
memory: 6940kb

input:

1
166347 18723
-1000 -979
-1000 -975
-1000 -928
-1000 -914
-1000 -898
-1000 -889
-1000 -876
-1000 -873
-1000 -858
-1000 -840
-1000 -838
-1000 -801
-1000 -783
-1000 -744
-1000 -738
-1000 -733
-1000 -713
-1000 -712
-1000 -695
-1000 -689
-1000 -680
-1000 -675
-1000 -671
-1000 -646
-1000 -643
-1000 -608...

output:

0.8514492

result:

ok found '0.8514492', expected '0.8514492', error '0.0000000'

Test #11:

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

input:

1
154903 84960
-1000 -979
-1000 -965
-1000 -956
-1000 -945
-1000 -920
-1000 -901
-1000 -878
-1000 -860
-1000 -858
-1000 -709
-1000 -693
-1000 -648
-1000 -619
-1000 -602
-1000 -579
-1000 -474
-1000 -473
-1000 -454
-1000 -443
-1000 -427
-1000 -407
-1000 -403
-1000 -384
-1000 -351
-1000 -279
-1000 -244...

output:

3.5389267

result:

ok found '3.5389267', expected '3.5389267', error '0.0000000'

Test #12:

score: 0
Accepted
time: 35ms
memory: 6620kb

input:

1
158037 96343
-1000 -1000
-1000 -905
-1000 -881
-1000 -833
-1000 -804
-1000 -803
-1000 -782
-1000 -775
-1000 -765
-1000 -759
-1000 -756
-1000 -748
-1000 -722
-1000 -674
-1000 -669
-1000 -630
-1000 -610
-1000 -573
-1000 -443
-1000 -411
-1000 -409
-1000 -403
-1000 -388
-1000 -366
-1000 -349
-1000 -33...

output:

3.9720288

result:

ok found '3.9720288', expected '3.9720288', error '0.0000000'

Test #13:

score: 0
Accepted
time: 37ms
memory: 4280kb

input:

10000
17 12
-853202371 684059854
-659446544 -924219854
-418025687 117998679
-399757126 -365708913
-331597239 -270896799
-204989763 869548983
-118492298 963842298
-77481232 672198731
45930201 -58234380
52605147 -900097542
78371985 940503934
235210685 595759114
391284089 234315077
416229789 -827244230...

output:

5.3985251
5.3739079
1.1735782
1.5443653
3.7782886
3.5704716
6.2829749
5.0959252
2.9875782
2.3055665
3.3907842
5.7854732
4.8109636
0.9567574
4.6294317
4.7995081
4.1702889
5.7394777
6.1210294
3.5674683
6.2280647
6.2825676
4.0146546
0.9004298
3.9943652
5.8905218
6.0623138
5.7850540
6.2831853
6.2652527
...

result:

ok 10000 numbers

Test #14:

score: 0
Accepted
time: 35ms
memory: 4256kb

input:

1000
133 108
-994106086 710243426
-991027749 -548437545
-983318226 -917527783
-943673956 -368162275
-935819096 616077188
-928022346 487569673
-924213856 -369318351
-914827619 426646545
-883935180 590882141
-870015071 -270471333
-834927107 -211343853
-829266515 354007200
-788041913 -60481736
-7822837...

output:

5.7428018
1.9153642
3.8043458
1.7919163
3.1695207
6.0786462
3.7860675
3.6659691
6.2265835
5.9021522
5.9443157
0.7151677
3.8315743
1.2228457
2.5984265
5.5473289
4.0791947
0.7042210
5.8578224
0.6894854
0.9379822
1.4215227
4.2713263
3.1189951
6.1809692
6.2831853
3.8988867
4.7914461
3.4519296
3.8385701
...

result:

ok 1000 numbers

Test #15:

score: 0
Accepted
time: 37ms
memory: 4304kb

input:

100
1367 924
-999416811 990355566
-997656126 346133696
-997071616 -657387469
-996176051 12622726
-995720693 334093112
-995478093 891631278
-994503890 341858449
-994297596 499383911
-993234202 533518057
-991636838 -4170504
-990563582 -407186200
-989454027 653116272
-989132124 -780605454
-988073521 -1...

output:

4.5051535
2.7125589
5.8396786
6.0229771
0.4616060
0.9869912
1.3219708
1.9258417
5.5086084
4.6463553
2.2876774
2.1848726
4.8094092
0.4770790
0.5563416
1.0936192
5.1827146
3.1131847
4.3802340
2.7492593
2.7917953
6.2717334
5.7538750
2.9007189
2.6393279
1.2526790
3.0746356
5.9400925
4.1734661
1.5164779
...

result:

ok 100 numbers

Test #16:

score: 0
Accepted
time: 37ms
memory: 6600kb

input:

10
13806 4955
-999669776 933068103
-999542354 721337508
-999499427 357140594
-999429088 -925180511
-999334813 -145726169
-999291694 -886327684
-999281647 811188099
-999145269 860687107
-998961821 -979442436
-998769313 446186367
-998591455 658309173
-998539751 -569480843
-998479467 279850955
-9984754...

output:

2.4170805
6.1611922
3.9600204
3.9943618
2.5515508
0.5227238
4.0978438
6.2103827
5.9817280
0.7772237

result:

ok 10 numbers

Test #17:

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

input:

1
112596 94970
-999980219 399324466
-999932413 952114487
-999894556 -951211102
-999891030 -996222974
-999864824 412806264
-999853190 -269700371
-999845814 -23906803
-999841507 -459154880
-999825178 716247149
-999761774 -154047106
-999729655 -171480333
-999709604 -666447277
-999704754 -22442485
-9996...

output:

5.4425939

result:

ok found '5.4425939', expected '5.4425939', error '0.0000000'

Test #18:

score: 0
Accepted
time: 45ms
memory: 6880kb

input:

1
161568 13252
-999991243 -113889211
-999976572 -361096764
-999970140 -505012445
-999960654 600963873
-999959339 -269932510
-999956568 734634576
-999941447 716485764
-999940305 64397798
-999939982 746532931
-999939921 995002380
-999932747 185078659
-999927136 585216518
-999914684 898656539
-99990452...

output:

0.6424746

result:

ok found '0.6424746', expected '0.6424746', error '0.0000000'

Test #19:

score: 0
Accepted
time: 51ms
memory: 7252kb

input:

1
186192 126483
-999998234 974001047
-999976292 -133179660
-999967957 112862981
-999957851 70030467
-999951528 743907713
-999931316 66002112
-999907988 888991267
-999905412 470798211
-999903986 -103943462
-999900422 255729004
-999898174 917068198
-999884392 -183592605
-999880179 -650076162
-99987469...

output:

4.4012457

result:

ok found '4.4012457', expected '4.4012457', error '0.0000000'

Test #20:

score: 0
Accepted
time: 28ms
memory: 4248kb

input:

1000
133 9
-10 -839744900
-10 -620593257
-10 -322048342
-10 578093727
-10 898998949
-9 -833794004
-9 -704882916
-9 -570204575
-9 -506146571
-9 -109555290
-9 309734100
-9 396668416
-8 -928874025
-8 376566668
-8 596463598
-8 600491164
-8 894775141
-7 -281322833
-7 49984651
-7 154512939
-7 205573228
-7...

output:

3.1415926
6.2831852
3.1415926
3.1415912
6.2831853
6.2831853
3.1415926
6.2831853
3.1415926
6.2831853
6.2831853
3.1415928
3.1415926
3.1415926
3.1415926
6.2831853
3.1415926
3.1415927
3.1415927
6.2831853
6.2831852
3.1415927
3.1415927
3.1415926
3.1415927
3.1415927
6.2831853
3.1415927
3.1415926
6.2831853
...

result:

ok 1000 numbers

Test #21:

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

input:

5
23120 8224
-10 -999575056
-10 -997485895
-10 -995458183
-10 -986953157
-10 -985268102
-10 -983223383
-10 -980910524
-10 -980404283
-10 -973605147
-10 -972441960
-10 -972440422
-10 -969122114
-10 -965754004
-10 -964812113
-10 -964558462
-10 -963159275
-10 -962972564
-10 -962085557
-10 -961552443
-1...

output:

3.1415926
3.1415926
3.1415926
3.1415926
6.2831853

result:

ok 5 numbers

Test #22:

score: 0
Accepted
time: 12ms
memory: 7272kb

input:

1
99995 60000
1 100001
1 100002
1 100003
1 100004
1 100005
1 100006
1 100007
1 100008
1 100009
1 100010
1 100011
1 100012
1 100013
1 100014
1 100015
1 100016
1 100017
1 100018
1 100019
1 100020
1 100021
1 100022
1 100023
1 100024
1 100025
1 100026
1 100027
1 100028
1 100029
1 100030
1 100031
1 10003...

output:

6.2831853

result:

ok found '6.2831853', expected '6.2831853', error '0.0000000'

Extra Test:

score: 0
Extra Test Passed