QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#704938#3627. Drugi DioTheZoneAC ✓336ms8124kbC++141.8kb2024-11-02 21:34:242024-11-02 21:34:26

Judging History

This is the latest submission verdict.

  • [2024-11-02 21:34:26]
  • Judged
  • Verdict: AC
  • Time: 336ms
  • Memory: 8124kb
  • [2024-11-02 21:34:24]
  • Submitted

answer

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int n;
const int N=1e6+5;
struct Node{
    int x,y;
}a[N];
double get_dis1(Node x,Node y){
    return 1ll*abs(x.x-y.x)+abs(x.y-y.y);
}
double get_dis2(Node x,Node y){
    return sqrt(1ll*(x.x-y.x)*(x.x-y.x)+1ll*(x.y-y.y)*(x.y-y.y));
}
double calc(Node x,Node y){
    return 1.0*get_dis1(x,y)/get_dis2(x,y);
}
double ans1=1e18,ans2=0;
bool cmp1(Node x,Node y){
    return x.x<y.x;
}
bool cmp2(Node x,Node y){
    return x.y<y.y;
}
bool cmp3(Node x,Node y){
    return x.x+x.y<y.x+y.y;
}
bool cmp4(Node x,Node y){
    return x.x-x.y<y.x-y.y;
}
bool cmp5(Node x,Node y){
    return x.y-x.x<y.y-y.x;
}
bool cmp6(Node x,Node y){
    return abs(x.x-x.y)<abs(y.x-y.y);
}
bool cmp7(Node x,Node y){
    return 1ll*x.x*x.y<1ll*y.x*y.y;
}
bool cmp8(Node x,Node y){
    return 1.0*x.x/x.y<1.0*y.x/y.y;
}
bool cmp9(Node x,Node y){
	return 1.0*x.y/x.x<1.0*y.y/y.x;
}
void solve(){
    for(int i=1;i<=n;i++){
    	if(i>1){
    		ans1=min(ans1,calc(a[i],a[i-1]));
            ans2=max(ans2,calc(a[i],a[i-1]));
		}
        if(i<n){
        	ans1=min(ans1,calc(a[i],a[i+1]));
            ans2=max(ans2,calc(a[i],a[i+1]));
		}
    }
    return;
}
signed main(){
    //freopen("apricot.in","r",stdin);
    //freopen("apricot.out","w",stdout);
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d %d",&a[i].x,&a[i].y);
    sort(a+1,a+n+1,cmp1);
    solve();
    sort(a+1,a+n+1,cmp2);
    solve();
    sort(a+1,a+n+1,cmp3);
    solve();
    sort(a+1,a+n+1,cmp4);
    solve();
    sort(a+1,a+n+1,cmp5);
    solve();
    sort(a+1,a+n+1,cmp6);
    solve();
    sort(a+1,a+n+1,cmp7);
    solve();
    sort(a+1,a+n+1,cmp8);
    solve();
    sort(a+1,a+n+1,cmp9);
    solve();
    printf("%.20lf\n",ans1);
    return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 332ms
memory: 7076kb

input:

300000
-601568508 -934354702
764555605 334850381
-65366979 -806773925
280528532 857572427
918818529 -505257461
930548215 927994285
-198460547 -332816017
-307890695 -780473866
-548201468 -26285710
287053272 353464207
-918802328 659705157
-969476051 -863520162
846779244 164231964
438876141 369069949
-...

output:

1.00000000000000000000

result:

ok found '1.000000000', expected '1.000000000', error '0.000000000'

Test #2:

score: 0
Accepted
time: 331ms
memory: 7336kb

input:

300000
937444316 799255993
-945764566 301212217
552929958 -321933395
-414574792 -880580853
9212831 -935966841
-201491071 -423230541
-345850667 -361110647
655070430 -375593617
-565863436 812506212
85158232 -646051394
124480822 -819139752
991164386 -312877718
511017755 -523573684
826901455 180322704
-...

output:

1.00000000000000000000

result:

ok found '1.000000000', expected '1.000000000', error '0.000000000'

Test #3:

score: 0
Accepted
time: 326ms
memory: 7840kb

input:

300000
-478499663 700948785
983017547 -762267974
528966015 -197383363
-163379064 822767550
898662985 584800266
-27179947 -521812240
589757877 -383916497
-349163685 -178616740
763260526 148678825
-975915986 -748033065
-924499432 -784299360
283015425 -822052342
750047251 -617797853
-931716830 -9310973...

output:

1.00000000000000000000

result:

ok found '1.000000000', expected '1.000000000', error '0.000000000'

Test #4:

score: 0
Accepted
time: 336ms
memory: 6576kb

input:

300000
526804367 -299902668
112258762 -699420276
947211034 -424669581
-956374742 603630449
371870510 -856066242
395734819 642924706
472852516 680017254
-89793686 -170222415
241125487 -930603924
340120429 59769607
-828824345 -281882602
-913698914 847128333
509263245 975387558
-958816781 -779136744
55...

output:

1.00000000000000000000

result:

ok found '1.000000000', expected '1.000000000', error '0.000000000'

Test #5:

score: 0
Accepted
time: 335ms
memory: 6432kb

input:

300000
-296134939 -834617014
-562000652 641099138
360488879 730435949
639917868 190581001
988264289 -962109587
-946243526 168496051
577192598 -876335584
96841378 164361180
-134393562 109268338
-246713617 -676499362
-995494108 202655496
-242077386 -740236084
860560128 -569459809
65807627 564438740
-4...

output:

1.00000000000000000000

result:

ok found '1.000000000', expected '1.000000000', error '0.000000000'

Test #6:

score: 0
Accepted
time: 326ms
memory: 7396kb

input:

300000
-445800 823611
850711 139919
-153310 -352410
379174 282862
-221038 -7668
54739 185715
-350848 -240278
-813850 -911287
822420 -494502
345092 -125416
110263 918578
-651550 -238390
-689877 -124927
767860 -875235
590872 -993004
-46754 -338576
-653041 -196043
801344 710001
967899 180518
-7137 -253...

output:

1.00000050043800836619

result:

ok found '1.000000500', expected '1.000000500', error '0.000000000'

Test #7:

score: 0
Accepted
time: 303ms
memory: 6584kb

input:

300000
-639993 479541
-565062 -22238
-305081 62044
788758 718979
418821 -555900
815329 -29511
233901 -266442
371157 186329
619712 -270011
17575 -713355
-387226 -319010
543470 325331
-750103 -811413
810381 -330239
-699678 -561573
172474 -339670
-565680 607412
-845556 645591
-330544 943202
364571 -911...

output:

1.00000050285356834046

result:

ok found '1.000000503', expected '1.000000503', error '0.000000000'

Test #8:

score: 0
Accepted
time: 306ms
memory: 7616kb

input:

300000
-508131 -217771
-595787 -646718
330090 477063
-376100 -247117
-674163 668004
-724711 862532
347750 890955
-767435 -955994
-546137 -662584
143633 -265863
529100 -941603
613054 -818531
30859 -568753
234945 619336
-241172 401408
-444873 250698
-816363 475693
-879668 -969921
-47244 260584
-217037...

output:

1.00000050148502261926

result:

ok found '1.000000501', expected '1.000000501', error '0.000000000'

Test #9:

score: 0
Accepted
time: 309ms
memory: 6976kb

input:

300000
-295545 129124
-964507 960799
992276 23050
197908 959819
661787 660513
-101521 971020
301335 -921275
-810672 818527
-195887 411619
299515 167043
-874167 -125746
117411 -448447
751890 -786621
28212 -204020
-495654 -491212
782174 208801
-845736 817667
169601 -337107
-159283 -116139
-377288 1885...

output:

1.00000050025100106765

result:

ok found '1.000000500', expected '1.000000500', error '0.000000000'

Test #10:

score: 0
Accepted
time: 309ms
memory: 7976kb

input:

300000
623057 -603657
-147418 -277659
-54290 222788
-716206 114674
582738 654947
-349237 -170031
-286183 -13598
648774 894209
-260155 -285152
-566012 -232645
343299 786629
247380 95994
-271418 821648
-713367 886794
841188 655598
-690269 464245
-948059 162313
-297062 514003
-614899 503084
145030 -515...

output:

1.00000050158890818608

result:

ok found '1.000000502', expected '1.000000502', error '0.000000000'

Test #11:

score: 0
Accepted
time: 310ms
memory: 8124kb

input:

300000
65440 6644
-189528 -214218
-167765 -63197
23726 -180270
-275276 8229
-163950 -39562
291375 26440
-213761 -28725
-78159 -59199
244753 101360
-77080 81872
-75280 -61164
-115938 165082
87837 -188676
194237 -58329
146712 -40323
164667 173536
45459 296902
-273309 285537
-267015 267768
-89882 -2146...

output:

1.00000166798854750461

result:

ok found '1.000001668', expected '1.000001668', error '0.000000000'

Test #12:

score: 0
Accepted
time: 329ms
memory: 7600kb

input:

300000
12650 34910
89295 -123631
-253177 43340
208585 194024
89529 81683
-81638 212166
15439 -161023
-34920 71669
-271864 -163190
-116522 186102
-281043 -241266
-151052 -58610
15440 183818
193174 27071
-139426 265839
-185770 173225
-82899 203525
-250406 -36075
-53135 174531
-142051 -263605
-43786 76...

output:

1.00000167074746726392

result:

ok found '1.000001671', expected '1.000001671', error '0.000000000'

Test #13:

score: 0
Accepted
time: 328ms
memory: 6324kb

input:

300000
-242349 -104173
-243800 -104011
22642 165090
-94436 108480
-19616 -297912
-45423 223580
-172369 -29570
215879 -273750
95588 -55754
66549 -230730
31556 45320
250813 233093
137700 90044
57823 137054
-176949 -267474
242644 -202945
-155295 298844
-6956 167347
80286 114960
-24173 277022
117048 146...

output:

1.00000166744063689883

result:

ok found '1.000001667', expected '1.000001667', error '0.000000000'

Test #14:

score: 0
Accepted
time: 311ms
memory: 7444kb

input:

300000
-216944 -297546
219341 -65214
133782 -120760
226255 126874
-82058 -297697
-18006 -37646
248774 -230486
-165111 -71730
-23884 -232580
283542 263239
208903 -174949
-188286 128436
-120271 227480
249300 81504
-67525 231677
-115633 -68117
150484 -196292
166670 -99382
-17052 92925
243845 117242
115...

output:

1.00000166888210761940

result:

ok found '1.000001669', expected '1.000001669', error '0.000000000'

Test #15:

score: 0
Accepted
time: 306ms
memory: 6268kb

input:

300000
37838 122138
-208208 222629
47156 296845
113765 -100688
-46068 184318
5130 121921
242465 156140
92104 212704
212819 -199087
292620 281006
-112517 5092
-20971 197020
-244330 -88247
246659 -173708
69609 -144219
25466 -192553
277919 33611
246429 25075
-53192 60194
140739 200740
-55488 -237779
22...

output:

1.00000166813045110459

result:

ok found '1.000001668', expected '1.000001668', error '0.000000000'

Test #16:

score: 0
Accepted
time: 283ms
memory: 7028kb

input:

300000
65215 133098
299033 95400
274811 206014
183517 223196
116258 284461
218040 142384
63350 136755
224232 144632
194088 65746
263339 213166
264731 284079
266781 284203
104683 211976
221818 89383
147481 115539
34301 54969
28866 226318
191724 42982
291957 31697
45750 251866
91661 242162
271693 1867...

output:

1.00000333703187704870

result:

ok found '1.000003337', expected '1.000003337', error '0.000000000'

Test #17:

score: 0
Accepted
time: 283ms
memory: 7880kb

input:

300000
198494 201361
133028 162767
66027 149342
257976 105620
176792 274518
141671 119282
260110 240740
160568 277157
197121 298317
28937 261167
256924 114864
46585 138150
187740 94987
264481 145110
48040 166294
178483 72937
134544 189792
21587 151555
217309 274637
161006 167712
29082 131343
255097 ...

output:

1.00000333596318413676

result:

ok found '1.000003336', expected '1.000003336', error '0.000000000'

Test #18:

score: 0
Accepted
time: 278ms
memory: 6924kb

input:

300000
259804 229647
202017 108510
30630 100520
4285 172512
39442 175468
185152 276614
10287 19720
97218 69105
80168 215045
267814 254449
55139 56219
236287 201254
194521 188290
299768 164642
121542 74324
131711 63372
35111 181577
279315 157627
47159 34447
290193 47237
254291 137383
239969 129913
22...

output:

1.00000333756648007721

result:

ok found '1.000003338', expected '1.000003338', error '0.000000000'

Test #19:

score: 0
Accepted
time: 272ms
memory: 7616kb

input:

300000
192352 58589
283047 202241
149388 135209
113935 182800
84477 142532
230275 282951
112301 29370
80635 251773
243803 108287
169331 176631
181303 210364
236460 19141
287465 151158
206971 210017
197581 289201
71748 276933
286518 61227
135732 244823
179372 13085
122970 17552
132805 16580
259427 12...

output:

1.00000333833527244032

result:

ok found '1.000003338', expected '1.000003338', error '0.000000000'

Test #20:

score: 0
Accepted
time: 276ms
memory: 7176kb

input:

300000
5679 136426
99379 81269
189303 220191
185046 293296
194546 279408
69291 3256
64782 134844
157792 282240
148120 3373
152972 248020
142093 282428
288603 290612
66495 49691
274383 72551
96826 227591
294907 167732
70143 26679
123705 8073
82782 179750
167545 162465
138722 156403
233710 264036
2565...

output:

1.00000333845786615328

result:

ok found '1.000003338', expected '1.000003338', error '0.000000000'

Test #21:

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

input:

13
5 11
11 10
4 4
2 1
3 3
12 8
10 5
7 6
6 0
9 12
0 9
8 7
1 2

output:

1.07959123809861967658

result:

ok found '1.079591238', expected '1.079591238', error '0.000000000'

Test #22:

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

input:

19
15 15
6 16
0 17
16 11
3 2
8 18
7 10
10 3
13 9
1 4
18 0
9 12
4 1
2 13
11 5
12 7
14 6
17 14
5 8

output:

1.06430416838038288674

result:

ok found '1.064304168', expected '1.064304168', error '0.000000000'

Test #23:

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

input:

16
7 4
11 14
0 6
5 1
14 7
1 8
15 2
12 11
6 12
3 0
2 10
8 15
9 13
10 5
13 9
4 3

output:

1.06870574981864474573

result:

ok found '1.068705750', expected '1.068705750', error '0.000000000'

Test #24:

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

input:

39
35 13
0 10
19 34
30 26
37 3
22 23
26 27
31 25
2 0
20 28
4 11
12 7
11 30
16 36
21 1
29 35
9 24
23 2
17 38
15 12
25 33
7 5
6 21
8 15
3 17
27 22
38 8
24 37
10 14
34 20
14 9
33 31
1 32
32 18
28 16
13 19
18 4
36 6
5 29

output:

1.02815186035957162325

result:

ok found '1.028151860', expected '1.028151860', error '0.000000000'

Test #25:

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

input:

22
4 0
17 1
2 4
13 5
18 16
6 21
20 10
14 17
3 18
9 7
21 15
5 13
19 19
12 3
16 9
0 14
11 12
1 2
7 8
15 11
8 20
10 6

output:

1.04643328713988692513

result:

ok found '1.046433287', expected '1.046433287', error '0.000000000'

Test #26:

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

input:

30
12 24
28 21
19 27
18 4
16 22
0 1
17 5
11 16
8 26
10 23
1 3
7 20
3 2
9 19
21 12
20 13
15 7
22 10
29 0
26 15
23 28
27 18
25 11
13 6
24 14
5 9
14 25
6 8
4 17
2 29

output:

1.03386827519336632619

result:

ok found '1.033868275', expected '1.033868275', error '0.000000000'

Test #27:

score: 0
Accepted
time: 82ms
memory: 4664kb

input:

94574
15404 91344
57085 34578
4969 40136
59527 11075
745 88040
35626 64946
21529 84741
35252 61104
12757 2235
81725 19336
38605 81601
64170 59356
51755 43619
11507 27964
92101 53492
6092 65672
66166 28949
83791 7003
54041 37572
22062 33017
89438 32051
89445 46099
69832 34547
10688 79799
24189 45431
...

output:

1.00001059451098295305

result:

ok found '1.000010595', expected '1.000010595', error '0.000000000'

Test #28:

score: 0
Accepted
time: 76ms
memory: 4568kb

input:

88953
30719 76075
36261 61477
14586 66661
37645 33582
11948 81894
85366 68278
44906 38175
32039 38104
61149 85371
4681 72309
988 59283
76664 51333
33630 86780
18370 8401
22322 14926
69965 50627
52324 10322
4285 88422
58729 19496
10429 85747
1874 4012
74505 14381
45053 73276
87855 354
85083 42449
687...

output:

1.00001126449599730961

result:

ok found '1.000011264', expected '1.000011264', error '0.000000000'

Test #29:

score: 0
Accepted
time: 79ms
memory: 6164kb

input:

93714
55886 48788
91909 33433
85712 69401
90905 79021
66874 59932
21406 59465
5270 7599
74777 82762
53868 49322
1995 57648
58610 65897
8511 43298
90970 22281
39880 70580
59751 46876
57766 64967
52455 4610
12807 89358
58363 70000
33067 38098
35629 1821
48666 50453
86020 83194
13137 66732
30680 62838
...

output:

1.00001068758583366858

result:

ok found '1.000010688', expected '1.000010688', error '0.000000000'

Test #30:

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

input:

54867
33923 5406
41731 31418
48092 51675
10287 51111
7030 12188
12274 8041
33656 51450
47159 4606
8158 52539
2338 1597
15402 51720
14841 39626
18676 22939
8617 53393
13131 14866
22247 13663
199 32544
4273 24413
53567 38723
29115 48462
54194 30798
54139 2576
39968 7915
31454 37037
45992 40096
29334 2...

output:

1.00001829575080725121

result:

ok found '1.000018296', expected '1.000018296', error '0.000000000'

Test #31:

score: 0
Accepted
time: 145ms
memory: 7872kb

input:

300000
0 0
100 100
200 200
300 300
400 400
500 500
600 600
700 700
800 800
900 900
1000 1000
1100 1100
1200 1200
1300 1300
1400 1400
1500 1500
1600 1600
1700 1700
1800 1800
1900 1900
2000 2000
2100 2100
2200 2200
2300 2300
2400 2400
2500 2500
2600 2600
2700 2700
2800 2800
2900 2900
3000 3000
3100 31...

output:

1.41421356237309492343

result:

ok found '1.414213562', expected '1.414213562', error '0.000000000'

Extra Test:

score: 0
Extra Test Passed