QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#55214#1340. All your base are belong to usckiseki#AC ✓1273ms3900kbC++2.7kb2022-10-12 18:54:082022-10-12 18:54:09

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-10-12 18:54:09]
  • 评测
  • 测评结果:AC
  • 用时:1273ms
  • 内存:3900kb
  • [2022-10-12 18:54:08]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
using llf = long double;

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);

    int n, k; cin >> n >> k;
    vector<pair<int, int>> a(n);
    for (auto &[x, y] : a) cin >> x >> y;

    auto f = [&](llf x, llf y){
        vector<llf> ans(n);
        for (int i = 0; i < n; ++i) {
            ans[i] = hypot(x - a[i].first, y - a[i].second);
        }
        nth_element(ans.begin(), ans.begin() + k, ans.end(), greater<>());
        llf s = 0;
        for (int i = 0; i < k; ++i)
            s += ans[i];
        // cout << x << ", " << y << ": " << s << '\n';
        return s;
    };

    //mt19937 rnd_engine(7122);
    //uniform_real_distribution<llf> rnd(0, 1);
    //uniform_real_distribution<llf> C(-1000, 1000);
    //uniform_real_distribution<llf> d(-10, 10);
    //static constexpr llf dT = 0.1, EPS = 1e-2;
    auto solve_y = [&](llf x) {
        llf L = -1000, R = 1000;
        for (int iter = 0; iter < 200; ++iter) {
            llf M1 = L + (R - L) / 3;
            llf M2 = R - (R - L) / 3;
            llf v1 = f(x, M1);
            llf v2 = f(x, M2);
            if (v1 < v2) R = M2;
            else L = M1;
        }
        return f(x, L);
        //llf y = C(rnd_engine);
        //llf S_cur = f(x, y);
        //llf S_best = S_cur;
        //for (llf T = 100; T > EPS; T -= dT) {
        //    llf y_prime = y + d(rnd_engine) * T;
        //    const llf S_prime = f(x, y_prime);
        //    const llf delta_c = S_prime - S_cur;
        //    llf prob = min<llf>(1, exp(-delta_c / T));
        //    if (rnd(rnd_engine) <= prob or S_prime < S_cur)
        //        S_cur = S_prime, y = y_prime;
        //    if (S_prime < S_best)
        //        S_best = S_prime;
        //}
        //return S_best;
    };
    auto solve = [&]{
        llf L = -1000, R = 1000;
        for (int iter = 0; iter < 200; ++iter) {
            llf M1 = L + (R - L) / 3;
            llf M2 = R - (R - L) / 3;
            llf v1 = solve_y(M1);
            llf v2 = solve_y(M2);
            if (v1 < v2) R = M2;
            else L = M1;
        }
        return solve_y(L);
        //llf x = C(rnd_engine);
        //llf S_cur = solve_y(x);
        //llf S_best = S_cur;
        //for (llf T = 100; T > EPS; T -= dT) {
        //    llf x_prime = x + d(rnd_engine) * T;
        //    const llf S_prime = solve_y(x);
        //    const llf delta_c = S_prime - S_cur;
        //    llf prob = min<llf>(1, exp(-delta_c / T));
        //    if (rnd(rnd_engine) <= prob or S_prime < S_cur)
        //        S_cur = S_prime, x = x_prime;
        //    if (S_prime < S_best)
        //        S_best = S_prime;
        //}
        //return S_best;
    };

    cout << fixed << setprecision(10) << solve() << '\n';
    return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 26ms
memory: 3724kb

input:

3 1
0 1
1 0
1 1

output:

0.7071067812

result:

ok found '0.7071068', expected '0.7071100', error '0.0000032'

Test #2:

score: 0
Accepted
time: 42ms
memory: 3900kb

input:

6 3
1 1
2 1
3 2
5 3
8 5
13 8

output:

17.5042561051

result:

ok found '17.5042561', expected '17.5042600', error '0.0000002'

Test #3:

score: 0
Accepted
time: 60ms
memory: 3764kb

input:

9 3
573 -50
-256 158
-751 14
314 207
293 567
59 -340
-243 -22
-268 432
-91 -192

output:

1841.2090392274

result:

ok found '1841.2090392', expected '1841.2090400', error '0.0000000'

Test #4:

score: 0
Accepted
time: 25ms
memory: 3796kb

input:

3 2
-319 -811
-864 -233
-465 -495

output:

794.4236904826

result:

ok found '794.4236905', expected '794.4236905', error '0.0000000'

Test #5:

score: 0
Accepted
time: 58ms
memory: 3744kb

input:

10 10
-698 -845
470 -24
-136 816
-671 806
769 253
-918 331
791 692
-43 958
-967 -620
-793 462

output:

8329.4386393095

result:

ok found '8329.4386393', expected '8329.4386393', error '0.0000000'

Test #6:

score: 0
Accepted
time: 48ms
memory: 3796kb

input:

7 6
-724 -599
899 -5
667 -707
714 -461
-597 938
-875 464
-857 65

output:

5742.9464651117

result:

ok found '5742.9464651', expected '5742.9464651', error '0.0000000'

Test #7:

score: 0
Accepted
time: 60ms
memory: 3788kb

input:

9 7
-60 -624
-429 43
748 -813
362 204
869 910
519 -883
-715 -646
-130 902
-255 -55

output:

6144.6664442504

result:

ok found '6144.6664443', expected '6144.6664443', error '0.0000000'

Test #8:

score: 0
Accepted
time: 17ms
memory: 3792kb

input:

2 1
-227 -556
-691 -537

output:

232.1944228443

result:

ok found '232.1944228', expected '232.1944228', error '0.0000000'

Test #9:

score: 0
Accepted
time: 50ms
memory: 3724kb

input:

7 5
-930 58
-255 210
16 -304
793 118
-315 -613
-266 677
903 -939

output:

4414.2615246168

result:

ok found '4414.2615246', expected '4414.2615246', error '0.0000000'

Test #10:

score: 0
Accepted
time: 67ms
memory: 3840kb

input:

10 3
800 945
510 -90
-624 -865
-318 336
-93 -791
162 750
827 295
-154 192
-565 -122
-719 904

output:

3305.8642072216

result:

ok found '3305.8642072', expected '3305.8642072', error '0.0000000'

Test #11:

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

input:

5 1
108 -850
546 -598
912 -508
-281 -729
368 822

output:

858.6496985844

result:

ok found '858.6496986', expected '858.6496986', error '0.0000000'

Test #12:

score: 0
Accepted
time: 20ms
memory: 3796kb

input:

3 1
-968 -448
-215 928
-747 -631

output:

823.6359936283

result:

ok found '823.6359936', expected '823.6359936', error '0.0000000'

Test #13:

score: 0
Accepted
time: 53ms
memory: 3864kb

input:

7 2
-567 390
286 -858
476 -258
858 456
528 -964
-358 704
-892 -913

output:

2221.8598065585

result:

ok found '2221.8598066', expected '2221.8598066', error '0.0000000'

Test #14:

score: 0
Accepted
time: 836ms
memory: 3792kb

input:

120 81
877 156
-561 -966
405 19
869 965
-620 -630
965 -498
330 417
-895 -943
610 -145
-468 535
590 -707
-388 -391
-468 610
-740 67
415 762
776 244
684 -457
570 -788
263 627
-727 897
737 35
-983 728
966 -493
-148 620
462 424
336 -507
741 -455
-877 -593
519 -101
-942 -758
-692 -826
765 -583
-572 -593
...

output:

75706.3968899319

result:

ok found '75706.3968899', expected '75706.3968899', error '0.0000000'

Test #15:

score: 0
Accepted
time: 305ms
memory: 3896kb

input:

45 25
-933 60
482 868
-834 855
571 691
-383 341
128 -126
601 -482
-497 335
-211 599
808 553
-625 -635
365 278
-104 -627
-447 -307
-927 -161
2 6
694 -185
385 685
46 214
-230 828
182 -686
891 740
-713 -377
56 -340
766 -277
-712 -790
630 800
-463 806
676 449
272 -798
-656 386
-718 53
-200 748
970 -853
...

output:

22730.8429385608

result:

ok found '22730.8429386', expected '22730.8429386', error '0.0000000'

Test #16:

score: 0
Accepted
time: 1223ms
memory: 3792kb

input:

198 148
251 -904
480 276
166 122
634 -606
-515 -541
132 -324
-450 -631
-405 -188
644 117
-87 -377
-277 -755
144 -401
-205 866
823 -88
161 816
506 923
-828 -648
999 -549
94 -248
-847 891
356 -777
-331 -316
734 418
-267 -599
-679 217
110 207
354 448
759 -699
153 353
-259 -542
-264 412
-437 441
913 428...

output:

130622.3594177271

result:

ok found '130622.3594177', expected '130622.3594177', error '0.0000000'

Test #17:

score: 0
Accepted
time: 730ms
memory: 3788kb

input:

117 80
422 -492
-34 -605
-373 -288
179 -841
117 73
901 -959
903 -882
549 165
603 860
462 435
383 435
-122 336
900 -292
-650 841
873 -768
-165 -905
716 -610
885 582
306 287
-178 -646
418 -887
-530 569
732 -936
-529 96
-61 377
-298 938
197 -734
-592 477
130 -622
-699 186
203 -966
-357 -695
-524 -453
6...

output:

74913.0994846239

result:

ok found '74913.0994846', expected '74913.0994846', error '0.0000000'

Test #18:

score: 0
Accepted
time: 221ms
memory: 3888kb

input:

35 15
-733 -972
774 663
779 -102
315 94
-514 459
98 -922
-373 20
-791 -460
983 445
32 145
-512 -615
-271 -784
-737 748
-938 -871
336 219
306 952
248 -690
552 -283
-219 -354
-117 241
437 -914
-533 529
995 -467
-5 -292
93 754
371 851
-252 422
-150 -957
-769 697
-961 380
-263 489
-778 -934
98 934
357 -...

output:

15788.7601753190

result:

ok found '15788.7601753', expected '15788.7601753', error '0.0000000'

Test #19:

score: 0
Accepted
time: 399ms
memory: 3848kb

input:

61 14
-686 75
-548 366
-829 -315
974 -218
-784 -344
801 797
-102 -391
-793 714
820 582
178 -877
824 -587
-807 83
264 213
-643 511
112 69
-148 -346
-679 783
921 30
-924 -865
867 -458
-967 144
-4 976
-722 -219
396 -914
460 -211
318 454
-503 -400
-689 -629
-921 -13
532 -434
-279 -207
-227 -132
798 -443...

output:

14955.5151415589

result:

ok found '14955.5151416', expected '14955.5151416', error '0.0000000'

Test #20:

score: 0
Accepted
time: 1202ms
memory: 3804kb

input:

184 84
-284 522
-782 503
-87 -614
-222 -653
519 620
878 841
109 -492
-646 592
-766 328
241 208
531 -900
-695 124
-447 24
288 -396
-666 709
937 -404
-92 -396
-505 478
-696 734
901 214
-798 -325
494 423
1000 239
-508 734
227 -138
951 -677
-116 -819
327 -708
791 -332
376 675
-447 -345
983 -405
-505 -19...

output:

84029.0451301769

result:

ok found '84029.0451302', expected '84029.0451302', error '0.0000000'

Test #21:

score: 0
Accepted
time: 1067ms
memory: 3768kb

input:

167 80
532 273
244 -311
-4 -61
700 -796
259 902
-83 -160
461 605
-97 -887
-809 241
918 802
-845 -356
-560 -425
-676 88
883 -668
616 -404
-140 -577
910 -673
150 938
405 875
-204 -640
-435 422
96 340
792 -409
-185 481
-684 -615
856 611
273 793
-907 -606
281 133
-110 362
-508 -276
216 -344
-427 725
472...

output:

80804.3962148285

result:

ok found '80804.3962148', expected '80804.3962148', error '0.0000000'

Test #22:

score: 0
Accepted
time: 40ms
memory: 3792kb

input:

6 3
-441 -239
694 -377
425 -769
-863 -138
208 915
24 -161

output:

2677.8910195586

result:

ok found '2677.8910196', expected '2677.8910196', error '0.0000000'

Test #23:

score: 0
Accepted
time: 695ms
memory: 3848kb

input:

115 18
-467 -968
293 -49
526 813
475 596
639 -600
-513 -680
168 624
311 689
570 618
-948 -425
90 782
-233 19
-223 19
-737 535
920 794
350 -171
-178 981
399 507
984 346
-910 413
-549 364
-108 685
199 -310
719 -219
-388 134
-266 -682
929 -722
878 -21
-486 -617
-8 214
605 -624
-839 -346
288 -90
668 400...

output:

20121.4315408133

result:

ok found '20121.4315408', expected '20121.4315408', error '0.0000000'

Test #24:

score: 0
Accepted
time: 9ms
memory: 3896kb

input:

1 1
-341 -447

output:

0.0000000000

result:

ok found '0.0000000', expected '0.0000000', error '-0.0000000'

Test #25:

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

input:

2 2
-325 -369
819 -604

output:

1167.8874089569

result:

ok found '1167.8874090', expected '1167.8874090', error '0.0000000'

Test #26:

score: 0
Accepted
time: 1221ms
memory: 3852kb

input:

200 1
-370 599
23 36
-737 489
798 375
-612 330
-366 -53
-449 -908
86 188
531 -427
502 839
-999 567
-487 27
-114 867
-893 -205
452 572
-339 455
-258 857
24 -737
903 633
-148 -61
57 -104
617 -379
128 -641
661 957
-760 -384
987 -59
707 119
-17 776
138 957
760 -61
381 242
-937 430
-654 -857
637 737
487 ...

output:

1277.3594278953

result:

ok found '1277.3594279', expected '1277.3594279', error '0.0000000'

Test #27:

score: 0
Accepted
time: 1128ms
memory: 3796kb

input:

200 200
588 -916
459 -468
222 -194
847 110
168 603
-406 980
-158 222
-691 -849
-424 -697
-102 682
-850 678
996 -741
993 -65
-126 -23
-708 -938
470 -284
534 232
379 -285
-368 915
616 930
-855 -954
567 -823
109 -292
843 -952
-827 -879
-210 46
-435 327
222 945
101 -468
-380 224
445 482
280 689
-348 -88...

output:

154043.1441555084

result:

ok found '154043.1441555', expected '154043.1441555', error '0.0000000'

Test #28:

score: 0
Accepted
time: 1217ms
memory: 3808kb

input:

200 10
282 -115
202 791
-242 -810
-480 -243
182 613
-605 732
732 133
848 866
886 50
-33 -166
-259 701
378 -558
-440 323
448 -275
-198 -144
375 -635
180 366
362 -319
-923 -658
461 -368
-128 100
445 -812
687 -667
-751 729
716 494
869 817
-528 -104
419 989
-334 576
652 282
684 687
-969 -169
-855 -125
-...

output:

12704.3193538440

result:

ok found '12704.3193538', expected '12704.3193538', error '0.0000000'

Test #29:

score: 0
Accepted
time: 1244ms
memory: 3836kb

input:

200 128
470 -675
-858 -644
993 903
645 68
274 -832
451 925
-572 -275
89 861
-322 -197
-431 -177
626 757
-94 888
-118 -854
-512 -95
-810 -153
-55 133
56 961
86 -877
-681 673
-879 -574
-663 -112
951 -752
430 745
119 -155
-321 -316
-608 -565
182 201
899 74
144 -422
893 -639
-742 -581
755 172
902 848
11...

output:

119639.0823971600

result:

ok found '119639.0823972', expected '119639.0823972', error '0.0000000'

Test #30:

score: 0
Accepted
time: 1273ms
memory: 3804kb

input:

200 54
-595 -575
-741 313
782 871
-332 -132
-326 500
-430 -934
-887 673
833 48
-406 -95
-591 -6
-430 900
-99 -56
229 -415
-358 965
211 259
-991 138
-154 10
965 466
-44 853
-139 467
-136 902
-297 182
-600 991
650 -609
103 -909
-636 164
481 893
444 -686
840 339
794 -501
-95 -631
648 687
-942 -798
153 ...

output:

59923.7798718836

result:

ok found '59923.7798719', expected '59923.7798719', error '0.0000000'