QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#249121#1340. All your base are belong to usAnwar_Gehad_Maghraby#AC ✓158ms3920kbC++201.8kb2023-11-12 01:02:392023-11-12 01:02:40

Judging History

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

  • [2023-11-12 01:02:40]
  • 评测
  • 测评结果:AC
  • 用时:158ms
  • 内存:3920kb
  • [2023-11-12 01:02:39]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
#define int long long

int n, k;
int x[205], y[205];

double dist(double x1, double y1, double x2, double y2){
         double dx = x1 - x2;
         double dy = y1 - y2;
         return sqrt(dx * dx + dy * dy);
}
pair<double, double> F2(double X, double Y){
         double sum = 0;
         int I[n];
         iota(I, I + n, 0);
         sort(I, I + n, [&](int i, int j){
                  return dist(X, Y, x[i], y[i]) > dist(X, Y, x[j], y[j]);
         });

         for(int i = 0; i < k; i++){
                  sum += dist(X, Y, x[I[i]], y[I[i]]);
         }
         return {-sum, Y};
}
pair<double, double> f(double x){
         double l = -1000, r= 1000;
         for(int i = 0; i < 100; i++){
                  double m1 = l + (r - l) / 3;
                  double m2 = r - (r - l) / 3;
                  auto f1 = F2(x, m1);
                  auto f2 = F2(x, m2);
                  if (f1 < f2)
                           l = m1;
                  else
                           r = m2;
         }
         return {F2(x, l).first, x};
}
void solve() {
         cin>>n>>k;
         for(int i = 0; i < n; i++){
                  cin>>x[i]>>y[i];
         }

         double l = -1000, r= 1000;
         for(int i = 0; i < 100; i++){
                  double m1 = l + (r - l) / 3;
                  double m2 = r - (r - l) / 3;
                  auto f1 = f(m1);      //evaluates the function at m1
                  auto f2 = f(m2);      //evaluates the function at m2
                  if (f1 < f2)
                           l = m1;
                  else
                           r = m2;
         }
         cout<<fixed<<setprecision(10);
         cout<<-f(l).first<<"\n";
}

int32_t main() {
         cin.tie(0);
         cout.sync_with_stdio(0);

         solve();
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3824kb

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: 2ms
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: 3ms
memory: 3820kb

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: 1ms
memory: 3880kb

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: 4ms
memory: 3848kb

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: 2ms
memory: 3808kb

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: 4ms
memory: 3812kb

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: 1ms
memory: 3880kb

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: 2ms
memory: 3904kb

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: 3ms
memory: 3864kb

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: 2ms
memory: 3920kb

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: 1ms
memory: 3832kb

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: 2ms
memory: 3876kb

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: 68ms
memory: 3820kb

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.3968899318

result:

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

Test #15:

score: 0
Accepted
time: 18ms
memory: 3872kb

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: 146ms
memory: 3836kb

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.3594177270

result:

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

Test #17:

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

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: 14ms
memory: 3896kb

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: 30ms
memory: 3836kb

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: 128ms
memory: 3820kb

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.0451301768

result:

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

Test #21:

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

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: 2ms
memory: 3820kb

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: 58ms
memory: 3884kb

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: 1ms
memory: 3864kb

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: 1ms
memory: 3876kb

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: 145ms
memory: 3864kb

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: 158ms
memory: 3836kb

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.1441555082

result:

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

Test #28:

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

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: 143ms
memory: 3820kb

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.0823971599

result:

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

Test #30:

score: 0
Accepted
time: 144ms
memory: 3812kb

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.7798718835

result:

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