Problem: ml_modeling (2022 finals)

You just landed a job as a machine learning engineer! As a ramp-up exercise, Boss Rob tasked you with modeling the watering wells in his yard, which can be represented on a Cartesian plane.

Boss Rob has a primary well at point \((A_x, A_y)\) and a backup well at a different point \((B_x, B_y)\), each able to water trees within an \(R\) unit radius. Using \(A_x\), \(A_y\), \(B_x\), \(B_y\), and \(R\) (unknown integers to you), Rob plants \(N\) happy little trees at real number points obtained by \(N\) calls to the function:

```
def gen_one_tree(A_x, A_y, B_x, B_y, R):
    while True:
        r = random.uniform(0, R)
        theta = random.uniform(0, 2*math.pi)
        x = A_x + r*math.cos(theta)
        y = A_y + r*math.sin(theta)
        if (x - B_x)**2 + (y - B_y)**2 <= R*R:
            return (x, y)
```
Here, `random.uniform(L, H)` returns a real number in \([L, H)\) uniformly at random.

In other words, he picks a point \((x, y)\) in the circular range of the primary well using the special method above. If \((x, y)\) happens to be in range of the backup well, he plants a tree there (else he discards it and tries again with a new \((x, y)\)). This repeats until Rob has planted \(N\) trees.

Given only the planted tree coordinates \((X_1, Y_1), \ldots, (X_N, Y_N)\), you are tasked to predict the exact values of \(A_x\), \(A_y\), \(B_x\), \(B_y\), and \(R\). As you are new, Boss Rob will accept your solution if it correctly predicts at least \(80\%\) of the test cases.


# Constraints

\(1 \le T \le 1{,}000\)
\(500 \le N \le 1{,}000{,}000\)
\(0 \le A_x, A_y, B_x, B_y \le 50\)
\((A_x, A_y) \ne (B_x, B_y)\)
\(1 \le R \le 50\)
The sum of \(N\) across all test cases is at most \(2{,}000{,}000\).

The intersection area of the two circular regions is strictly positive.

Tree coordinates in the data were truly generated using the randomized algorithm as described above. The secret parameters \(A_x\), \(A_y\), \(B_x\), \(B_y\), and \(R\) have also been chosen uniformly at random for each case (rejecting cases where the circles are identical or do not have positive overlap).


# Input Format

Input begins with a single integer \(T\), the number of test cases. For each case, there is first a line containing a single integer \(N\), the number of planted trees. Then, \(N\) lines follow, the \(i\)th of which contains two space-separated real numbers \(X_i\) and \(Y_i\), each given to \(6\) decimal places.


# Output Format

For the \(i\)th test case, print a line containing `"Case #i: "`, followed by the five space-separated integers \(A_x\), \(A_y\), \(B_x\), \(B_y\), and \(R\), in that order.


# Sample Explanation

The first sample case is pictured below, with the primary well's range in red, the backup well's range in blue, and the \(500\) randomly-generated trees in green:

{{PHOTO_ID:6502772429739994|WIDTH:700}}



Sample input:
2
500
18.243577 16.343618
24.560940 7.478552
13.664297 0.348593
19.766713 16.871980
14.052491 10.567715
21.426414 5.786941
20.495098 -0.246197
20.706538 14.324784
13.240629 9.591812
18.131521 1.645394
13.085966 5.206907
12.705525 2.340957
17.081302 -3.503313
17.406894 -4.132649
18.662161 14.841332
21.722473 13.853187
12.566132 7.860660
16.422074 12.005824
17.360418 15.791112
17.109026 7.669767
18.253835 6.466656
21.249345 1.667549
21.665745 0.311747
16.095203 14.907657
15.823431 -4.340649
14.764783 -3.979121
12.216653 2.449552
12.283698 8.764607
17.379537 14.086718
11.356151 4.039189
18.250737 10.348279
18.803695 -3.124892
17.208013 -1.383813
15.846419 7.176925
12.209281 2.863600
19.786703 12.537685
23.019766 11.553517
12.677512 3.801674
21.313409 10.926474
13.065841 -5.327402
23.974605 10.274300
14.052084 5.745476
12.344311 4.014428
13.824721 3.340018
21.333789 16.244543
22.993558 3.915954
21.482560 16.650764
21.423192 9.596803
17.471653 -2.073008
19.254667 10.037329
13.026102 2.910256
19.164159 15.152278
15.448711 5.268898
22.436500 6.103729
18.713233 -0.696114
17.319829 -4.614399
16.303121 6.662335
18.549615 9.323836
20.578796 13.197413
20.101191 10.285048
12.731656 6.398406
15.642672 12.203354
11.739751 -2.209279
19.999162 12.495027
13.332741 -0.781345
16.419368 4.930287
14.208240 6.146094
12.668535 3.884128
17.100494 9.477584
15.298066 2.105778
21.715575 3.461332
13.812862 -0.393683
15.197469 3.227296
17.805714 12.076443
14.894292 -2.076883
11.362856 0.971215
11.152936 -0.329086
24.312335 12.223521
23.850104 13.665174
13.611467 7.009552
22.958613 10.937624
17.476002 5.911470
13.385598 8.687516
15.245710 4.570724
17.698810 15.101508
14.683332 8.660956
17.830283 14.623531
11.844331 0.565127
22.538936 14.469856
14.570230 -2.940471
23.501721 7.793592
22.580591 6.388695
17.440296 5.839274
17.532098 6.355300
16.728496 6.375671
18.752338 6.307287
21.240144 10.501905
14.970281 7.859548
15.357577 -4.434922
16.310483 -1.394290
22.759885 9.828241
14.186619 5.960630
24.193644 14.368893
17.442571 12.499045
13.034105 -6.500657
17.697254 11.737589
13.480724 -3.930224
22.150737 17.126988
13.391916 -0.925885
23.572665 4.572828
15.420402 8.829672
16.683175 5.409393
20.887778 5.088725
13.519647 4.812447
17.129407 -1.925479
16.603673 3.593709
22.113753 16.325847
13.066364 2.073991
15.710264 8.778860
17.767049 8.993840
11.706371 -1.170487
11.470356 2.861039
17.231284 7.889578
24.189637 14.224167
19.075589 11.166930
20.937783 13.154556
23.523316 12.300135
14.445991 11.359735
19.239496 12.970156
21.742953 4.547351
12.910622 1.840402
21.075760 6.167560
13.244078 -2.969471
13.140408 -6.471153
20.315724 14.875012
23.818682 11.079752
17.887454 -2.232520
18.666566 0.092412
14.317916 -3.570190
15.472072 -2.829925
21.556983 0.279414
22.036423 1.708065
14.568483 0.688430
19.482935 8.690586
17.496132 11.691013
15.570701 5.436852
18.179237 -3.363174
14.980168 8.543218
14.915177 -0.184438
14.969153 0.104570
14.067303 7.651140
14.964894 0.975905
20.284008 6.167394
22.797939 6.211927
16.313922 14.186456
14.834579 12.685060
21.480677 2.065544
12.584922 3.150118
13.136840 0.802224
11.390730 -0.761440
17.002476 5.312136
20.846441 4.748559
17.902435 4.933033
14.915677 3.063146
14.466079 -3.505656
16.495423 -0.516658
15.123951 -1.633273
19.347161 16.123210
24.262812 13.836784
16.744183 13.521877
13.795204 4.941614
15.614470 12.670248
14.141935 9.959788
11.217067 4.675771
12.697649 -0.067208
19.514341 13.742676
16.637732 3.278594
21.107319 14.689994
17.380294 10.999330
20.672382 14.136265
11.533785 2.455757
21.634049 10.042583
19.865202 14.092486
22.647324 17.180916
13.916645 2.700255
21.097245 12.705439
14.797356 -2.723860
15.674174 -1.807078
21.891569 6.225470
18.340370 9.365718
17.377817 6.161102
15.117478 0.715163
18.782919 3.899382
13.107155 7.205792
18.844233 16.639468
18.316959 -1.084489
16.864189 6.381003
17.413163 -2.782152
18.155452 7.203062
22.653910 1.225094
15.276962 6.826973
19.467625 4.793109
21.273117 10.211036
13.053714 4.142984
11.594127 1.722787
17.187284 5.900224
20.751730 5.502650
19.298775 7.373680
20.090593 -1.788020
22.540876 13.519997
11.735849 2.496556
16.109133 14.156335
19.604004 11.711670
23.481796 4.654737
18.756305 8.135686
20.751269 0.800819
14.073437 7.240697
17.022144 7.532538
14.800061 10.052073
19.638047 3.327763
19.495916 9.221839
11.418687 -1.636822
16.627811 3.856185
22.189477 18.520143
19.746557 -1.725730
16.438720 10.266559
19.785090 6.069816
16.417114 13.062245
15.667475 9.619686
19.909511 5.066407
20.251697 17.418113
22.658481 18.376700
11.513801 1.356283
18.258572 2.014423
17.457905 7.408070
21.347081 10.562006
12.259695 0.465383
11.687451 2.106452
14.026429 -5.711334
15.410070 -4.322808
16.792314 0.508719
20.651046 7.219566
14.634011 10.399200
12.405734 -2.693974
14.716979 -3.275552
13.872859 -2.763565
22.064022 11.633544
15.729799 10.378849
19.310824 0.908302
11.290350 5.008839
17.987185 11.212424
18.933293 11.589430
24.225082 14.074144
14.280323 2.518275
23.126585 8.980823
15.261063 1.383509
22.828022 17.600195
12.454820 4.367434
18.535066 3.691446
20.314638 18.047548
23.145756 15.102703
13.296147 -6.688498
21.647239 1.718656
24.121364 15.219336
13.194050 8.691127
11.766890 5.884297
18.217592 14.226418
17.915127 2.176438
14.634272 -3.488542
20.234345 0.554279
17.188012 7.985024
17.346218 10.995344
18.669436 2.636653
18.951858 11.670444
13.285687 -1.499801
22.001488 14.067161
22.770735 7.750486
12.963328 5.944176
20.682994 15.335158
11.114365 0.432639
23.735128 15.517813
22.032538 6.398391
15.201702 -3.937585
18.687441 15.891635
14.161156 9.388260
13.996130 4.657658
22.323146 6.098112
20.934790 10.211547
16.590131 5.371991
20.039944 12.763506
14.652548 11.006175
19.154292 4.181016
17.199467 2.304127
14.206927 9.107424
19.143110 4.677616
21.210108 11.776738
22.448183 9.536389
24.468761 12.923552
19.753874 2.928480
15.879698 8.601265
21.579355 10.235260
12.337658 8.782207
16.823056 1.073752
23.213925 8.143511
18.283541 10.342998
21.109487 4.830167
20.576977 18.388817
17.305744 5.831552
15.129693 5.247627
16.948835 11.394945
11.708893 -1.237782
11.640301 0.735272
18.564261 7.765312
15.367225 12.715984
17.515852 13.448675
18.427577 -4.113174
16.063344 4.479923
19.850385 13.378851
17.990363 11.657032
17.696624 0.518123
20.326250 10.275394
16.374879 6.186846
12.339243 3.446059
19.054799 -1.407273
22.345393 0.656893
12.027935 -0.424062
23.649456 5.875965
16.363737 13.309612
15.567342 13.854572
19.403075 -2.105705
22.961203 12.299632
14.376183 7.683317
17.591174 13.661803
11.394050 0.175477
14.569772 4.742531
15.213890 2.957571
23.610500 15.936788
14.141149 1.670263
18.528925 11.541278
23.898984 9.211051
13.211419 10.291301
22.984657 14.996915
16.231052 -2.488522
20.056612 8.249936
11.894928 1.368478
24.280032 9.901244
13.543034 7.292310
21.466143 6.122634
17.050924 10.602068
14.559508 -2.832191
16.002019 14.311328
15.689925 -5.344107
18.137508 11.902096
21.828029 6.265151
12.626233 5.939640
19.495225 -2.888468
14.731963 5.949898
14.539116 3.761306
13.563525 5.118103
20.781815 4.269694
14.646917 3.059797
19.582913 9.167719
11.998265 6.262899
18.248830 15.023882
17.738511 -3.775898
20.613168 8.945199
11.812803 0.311242
24.163159 5.006179
21.371522 18.282868
14.865494 13.354208
18.606131 3.411418
20.882197 6.015836
21.219685 1.104721
17.830305 11.210971
19.458500 -0.184236
11.294817 1.942603
19.357381 11.114160
14.342764 -1.600163
13.078637 1.105681
16.311977 7.151695
18.727277 4.389283
20.787157 9.958316
20.703801 2.179316
16.405388 -0.443747
23.490212 13.183778
14.704340 6.400590
12.762951 9.163493
14.879646 8.827834
21.287460 14.149522
11.842059 2.628325
17.880290 15.006137
18.488039 13.571962
16.821542 1.475234
20.002707 7.186862
21.002156 3.685887
22.249825 5.127291
19.210100 2.009205
17.068320 14.565406
22.923564 9.027532
12.761185 6.521029
16.884040 -4.998579
11.380716 1.854268
21.946966 11.675032
14.934287 1.053398
15.176332 8.083325
22.785108 3.453335
13.580786 -2.436422
12.008668 -0.448807
22.285708 6.989855
11.515857 6.041525
15.121135 -4.946932
22.928785 3.446890
21.326448 1.359870
22.521962 12.562228
21.165139 8.573858
21.684998 17.690259
14.438082 5.794504
21.031054 9.259496
17.279543 -3.524403
19.916938 2.219192
16.274795 13.211478
22.838144 13.435671
21.410865 10.932324
13.968554 2.445044
17.281427 5.253919
11.785362 7.062835
19.891893 4.854905
22.357187 10.673764
20.926022 17.195318
12.342682 7.376183
17.739443 14.821393
13.242037 4.155476
13.216160 9.938764
15.535745 9.586368
11.720537 5.201965
18.051503 5.764098
14.760959 -1.865235
16.287678 13.346010
12.837573 -4.549325
18.912745 6.950515
21.757445 2.312409
17.617996 5.427429
18.643869 -1.983641
20.721220 4.218309
15.411880 2.817564
16.139809 -3.232530
23.725701 13.763255
16.011610 -4.548052
15.915922 -2.430327
11.575523 0.684496
15.099677 -4.363962
17.991955 8.201164
18.803073 2.670414
16.811572 12.341744
12.941817 -2.988387
22.065002 9.335321
14.385033 -2.828393
14.482881 4.155121
11.368385 3.728045
12.616389 5.472795
13.723615 1.901616
17.134331 4.595940
18.927768 4.830461
18.909544 -1.361066
11.543834 6.117217
18.542131 14.676562
17.502316 10.484115
20.258744 7.166175
14.160867 2.204443
14.790041 -6.095155
22.782137 8.059894
16.203873 12.718181
17.034161 7.989151
19.991610 8.234883
12.719392 5.517438
20.999982 17.261621
20.469714 2.621880
18.234895 15.202904
16.422493 -3.498837
16.596906 3.914879
14.752444 -0.821616
15.314792 11.415450
12.851978 9.336743
21.322624 13.745326
13.786509 8.308467
17.942216 12.143173
17.073233 6.949597
14.640306 6.576499
14.271760 -6.901011
22.238735 13.842624
14.931032 10.612377
19.888461 12.948929
23.220118 17.001903
20.177677 17.873523
15.306416 12.140175
12.881961 -1.375601
15.604397 6.135945
20.500871 16.129972
14.722210 2.613046
19.842808 8.445985
500
39.710957 45.266595
41.094057 48.798544
32.730857 56.546952
39.923442 50.088557
31.605212 50.959184
44.136309 48.892818
40.679879 53.937977
36.294096 47.800636
40.113173 50.213649
45.815416 49.890518
35.390036 51.205328
40.179830 56.875049
43.017164 50.051028
49.406105 49.928356
39.677790 50.945483
30.190194 51.691234
41.459104 50.089287
38.109223 49.793925
41.014266 48.975303
39.618398 49.872185
39.178027 41.046407
41.431534 54.213090
38.964825 49.047545
38.658587 38.203762
47.028748 50.926262
44.946954 55.941038
41.748067 50.327319
40.402357 52.302971
37.396668 49.029110
39.970103 46.738960
41.557000 49.028231
46.653893 51.850747
34.323012 38.342964
36.171351 40.954143
39.214588 49.000613
41.740162 43.060434
38.431705 46.437356
39.979116 49.952087
36.978888 39.194257
46.443834 49.909108
40.480895 52.766131
45.754379 46.547171
42.166935 46.402821
48.080283 41.894377
38.246017 43.416761
41.953040 50.476751
39.865857 49.530552
41.857377 50.013353
44.380329 46.520652
35.459070 54.378871
43.232534 48.169888
39.632352 42.449325
43.925993 47.340151
37.698824 44.739390
28.184573 52.497879
38.538581 50.028130
40.521712 50.372595
35.229803 49.007954
43.099286 47.894280
38.542279 56.193252
41.871149 54.439086
46.674640 48.198138
46.205344 49.817384
30.971898 55.545589
41.559736 38.994530
40.177922 37.904946
30.494785 48.157057
35.719292 46.167523
45.530931 39.738645
42.873389 37.980906
31.878676 44.846620
48.186863 47.771724
29.228833 46.725250
45.223304 50.998057
47.870020 49.148890
39.352382 54.673676
40.148100 47.892058
44.647657 53.001798
46.614089 53.399927
40.663255 50.223452
42.640232 52.380332
43.778852 48.694217
34.158139 50.997053
41.136006 49.992605
40.053666 49.921808
35.225913 46.713783
40.601042 50.439770
41.586720 48.240993
39.443384 52.084739
34.596839 54.522052
38.969216 50.791696
39.049111 50.254377
37.013686 50.373442
32.414501 39.750556
32.434373 47.907422
39.854269 49.799558
45.722175 47.402687
38.153656 50.675492
41.137037 51.734551
45.508697 45.788019
38.247781 52.070213
39.939174 48.752783
42.506471 48.492028
37.919994 53.660953
40.172611 48.041809
39.614792 47.091801
50.201163 48.560086
43.357359 53.958365
40.194645 50.406657
40.354321 46.381505
35.903486 48.114179
38.386775 56.259680
40.357767 54.203151
43.972331 47.069318
47.446154 51.523650
32.359882 41.212162
38.732705 42.740130
39.463927 47.524004
42.812980 55.454894
41.795590 49.173620
39.032718 50.273038
32.518649 48.442989
40.839095 50.473562
40.410917 48.100713
35.130014 43.156838
39.249088 57.935378
40.779368 52.280509
41.615880 50.993354
36.334769 56.266999
36.601264 42.388724
34.944154 41.799126
42.854057 52.162139
33.152265 44.680723
34.271882 53.290670
41.475050 57.238456
39.932776 50.705882
48.979293 49.011608
39.305110 49.793842
35.442708 52.646366
39.889823 50.072493
37.582594 44.403575
44.259902 52.119507
33.297470 49.354147
33.461744 46.894107
39.409612 54.773790
35.086432 51.758613
40.290717 51.729781
37.038409 45.767644
40.629452 51.952247
43.559446 53.269191
37.350402 50.836273
41.022322 54.801113
38.840797 51.618559
39.128142 50.178447
48.635788 47.819744
41.778652 47.256399
39.073664 51.113564
39.865049 47.329230
39.979471 50.040133
41.071938 53.165958
39.924370 50.050306
40.422036 40.620715
46.308078 50.771640
31.790126 56.360747
34.955053 44.626032
37.504998 56.239796
40.213975 50.612955
41.205129 49.902843
34.036798 44.778043
48.385887 48.505653
40.440069 50.654286
31.760689 53.120080
36.559574 39.373117
40.738227 49.175229
38.242645 56.969227
40.040945 49.546137
39.340671 56.635673
37.819319 43.171628
35.120439 50.036466
41.312137 51.650149
45.160639 39.138498
42.562569 46.601520
40.309043 40.357372
35.174605 50.761648
41.057364 52.244331
39.940033 50.084898
44.595424 49.420787
30.067301 55.155793
45.865714 48.211928
37.409045 52.919590
49.661212 49.376667
42.498227 45.363746
39.886511 50.012223
46.096362 54.275603
35.947168 42.034252
36.432942 44.574235
34.362423 46.302890
38.119111 54.078242
37.747013 54.868288
31.873562 45.516690
32.515813 53.516542
39.671665 42.871466
33.579744 40.047387
31.576114 54.361684
41.452554 52.385149
40.462635 48.856155
40.353170 50.189707
34.169142 54.262581
30.950592 42.675391
35.575152 51.110144
46.128889 45.104205
36.157801 49.820947
37.006649 47.203003
44.464543 56.140591
41.286502 51.738602
38.099177 57.013475
46.631406 47.176450
45.046065 40.843340
36.725044 49.700036
40.138197 49.875275
35.599979 56.208785
47.168374 52.655980
39.894782 50.020758
36.007925 41.739840
33.860398 54.502449
47.340651 51.076716
38.239283 55.920821
38.124766 49.978608
41.136594 48.377128
29.427001 48.240045
28.108165 44.835984
34.427556 49.470320
40.059227 49.550819
38.001566 56.703105
39.974419 48.997753
48.870087 49.093396
40.212240 53.272341
39.789322 52.876445
40.845778 38.101325
45.696749 44.896706
42.170637 47.468178
45.003262 47.392827
42.789490 46.174756
40.136490 49.363977
40.922267 49.030949
49.333579 46.468735
45.022548 47.906167
43.637612 52.857929
47.268117 47.519882
41.272130 54.197584
34.082949 43.254136
38.036205 40.661918
42.655798 41.576628
29.807866 47.872254
28.601989 46.178377
45.411278 45.931233
32.453695 55.680718
40.016094 49.898548
31.326411 50.604130
42.541382 46.391883
28.142174 45.606911
42.148711 43.006960
31.308546 53.696334
45.323549 48.297625
41.814194 53.978169
46.899230 47.272690
38.927142 48.380082
40.496094 50.455800
29.517210 53.065575
39.362424 50.197373
41.328216 50.818224
45.522371 52.786934
37.901221 53.182777
33.441511 53.449409
41.329462 48.275714
36.578736 50.137690
29.935958 48.603522
39.120310 43.660767
36.182135 55.431890
39.146117 43.984569
40.997061 38.106491
35.989093 46.728348
37.448224 53.295281
40.814741 49.310066
31.784712 52.810431
48.970584 43.550682
40.665791 48.928635
37.455128 44.746699
46.152666 48.957633
30.336969 48.234010
32.695164 51.864903
31.589178 43.457383
46.147549 53.306138
31.999644 52.420644
37.882452 52.135957
40.844183 49.988777
36.467747 48.329731
40.117265 49.605837
39.689079 49.782545
38.403469 54.554917
40.421711 49.109454
35.043304 45.353460
37.700068 47.538726
48.128997 49.081839
42.460803 40.752714
37.235602 50.072579
45.674603 44.480303
37.349137 46.221747
44.085857 39.527531
39.451587 49.957036
34.806971 49.046043
35.529302 51.253406
40.190963 49.973052
39.633260 47.552746
35.453864 43.969233
34.274948 53.082556
39.463399 50.393113
37.957584 45.630232
37.322489 54.006826
44.606528 41.399097
39.411046 40.458141
31.338206 50.536917
31.136214 43.527204
45.798060 50.822431
34.871658 50.062171
35.844121 42.638803
34.872808 41.204881
43.755368 51.614795
38.982354 49.926225
40.469698 48.179031
35.913369 43.066653
42.528609 45.767257
48.618570 46.356773
27.872295 52.528578
41.715208 51.600960
41.181149 53.685790
39.303489 53.892835
39.293418 48.153534
41.756249 51.245006
31.774363 44.426609
34.861405 46.757609
40.802245 48.921425
43.937823 48.149107
39.046799 51.495534
44.164015 47.377663
33.810651 55.003684
34.927154 47.447552
34.035538 44.333249
37.871520 39.762833
40.666335 49.469386
36.616461 47.193929
30.155009 55.226397
38.487555 53.622646
40.997810 42.076416
45.945407 44.422717
41.899604 45.437848
35.851069 39.610831
35.506742 46.914798
44.438356 53.799029
39.989213 47.854211
40.688131 48.384774
34.652201 50.303544
33.755665 45.964317
40.030597 38.511805
40.496887 49.662393
38.227873 56.650526
42.024271 50.307892
40.098551 51.020802
37.124217 56.020006
45.573360 49.079709
38.113194 47.452914
41.032388 49.568862
40.468636 41.700309
37.471402 53.415458
41.048122 50.915859
34.495824 52.399788
36.448848 47.859274
39.011571 45.145133
40.775737 54.882725
29.285397 47.497443
39.026980 50.093095
47.015660 53.027474
34.763263 40.445794
36.897710 46.648874
40.241097 46.761277
48.060150 52.452125
40.306719 47.029494
42.084311 49.727923
35.976952 56.782986
47.126106 49.162825
37.897456 51.564894
36.654695 50.819627
40.781800 53.945677
41.842433 53.752172
41.589129 53.110102
32.761789 44.088345
41.719804 53.989094
36.944823 45.053298
42.827828 46.842898
41.016473 46.911213
38.918312 54.211936
37.981049 47.710730
39.890346 50.385934
44.764060 50.488667
40.308209 49.871190
38.160808 41.818470
47.957911 43.210035
43.687500 51.766336
41.918077 50.059497
31.679299 54.296609
45.771261 49.218397
38.123103 57.954250
36.124360 38.699324
32.968935 45.593800
36.560694 51.382055
34.735064 40.361008
32.251581 42.107719
44.199665 41.877420
41.143788 50.764761
33.338016 46.664050
49.922917 42.219510
50.478030 44.841695
39.976942 50.064551
34.875631 50.503983
47.770352 41.098315
38.284620 54.466581
46.593736 53.092283
39.045259 51.162862
39.613480 49.903060
29.546920 50.066181
41.943758 43.196521
37.059391 50.779753
39.992419 49.911640
47.980034 43.365287
34.320640 40.515435
42.231814 47.944971
43.508937 52.307746
39.973595 46.291718
44.220332 52.161464
41.159619 40.973367
47.101236 49.724113
39.782978 50.204596
39.559919 49.480320
36.835299 48.650068
37.883515 44.698028
44.397487 41.980311
34.290696 48.708611
36.936342 50.120652
41.121951 52.657115
43.518312 44.024548
39.437155 52.745160
39.835412 46.283453
40.310665 48.125508
45.963017 48.159980
38.177037 51.293065
45.889694 55.310913
42.049010 49.604768
28.899711 52.311737
37.241460 44.649299
33.318865 47.628176
40.966198 51.913582
40.366353 49.362066
29.296032 49.797302
43.173336 52.250949
47.690825 49.396015
33.643206 43.968056
30.131878 46.189694
33.388653 54.541037
32.137200 45.597199
39.122132 49.672227
41.584771 56.233178
36.580879 44.724607
39.466947 51.197577
37.561921 47.022670
42.761769 48.915168
39.787125 44.289218
45.484312 43.809723
41.811338 48.622222
37.213599 49.935951
39.942045 49.772859
49.891856 42.872467
31.964570 45.776619
40.171680 49.987490
37.038137 52.940678
35.265299 47.478347
44.996427 49.981928
39.734830 54.125940
40.304740 53.221447
38.560754 46.599124
39.647909 51.223265
36.609585 37.915030
34.542710 46.975530
40.441693 50.006388
34.944957 44.328503
47.217304 47.688772
38.580101 51.789895
41.506001 49.071389
42.049850 50.259588
34.832636 47.585776
42.867048 45.434276


Sample output:
Case #1: 6 10 30 2 19
Case #2: 40 50 38 45 13


Solution: There are many ways you might approach this problem, but a simple one is to find the pair of circles that contain all the given points while minimizing the area of the intersection.

A naive solution tries all ~\(50^5\) possible pairs of circles and does an \(O(N)\) check to confirm that all of the points lie in the intersection of that pair of circles. Even if we downsample to \(500\) points (the minimum guaranteed by the problem), that's still too slow.

We can do some precomputing to make this much faster: for each possible circle center \((x, y)\), the only radius \(R\) we would ever want to use is the smallest one that contains all of the points. This gives us at most \(51^2 \approx 2{,}500\) possible circles to use, and sometimes fewer because \(R\) will be greater than \(50\) for some choices of \((x, y)\). 

Now we can simply compute the area of the intersection of each of these \(2{,}500^2 \approx 6{,}000{,}000\) pairs, and select the pair with the smallest intersection. If we encounter a tie, we break it arbitrarily.

Once we've decided which pair of circles to use, we need to decide which one is \(A\) and which one is \(B\). While the function for generating tree locations may look like it spreads trees evenly across a given circle, it's actually biased towards placing trees towards the center of \(A\). The function generates \(r\) uniformly from \([0, R)\), which means (for example) that half of the points will land within a radius of \(R/2\) which is only a quarter of the area of the whole circle. If we compute the sum of distances from each point to the centers of the two circles, the circle with the lower sum is more likely to be \(A\).

Empirically, this approach correctly predicts approximately \(90\%\) of the cases when \(500\) points are sampled.


Code: #include <algorithm>
#include <cmath>
#include <iostream>
#include <tuple>
#include <vector>
using namespace std;

const int SAMPLES = 500;
const int BOUNDS = 50;

int N;
vector<pair<double, double>> P;

inline double distsq(double dx, double dy) { return dx * dx + dy * dy; }

bool check(int x, int y, int r) {
  double Rsq = r*r;
  for (int i = 0; i < min(N, SAMPLES); i++) {
    if (distsq(x - P[i].first, y - P[i].second) > Rsq) {
      return false;
    }
  }
  return true;
}

void solve() {
  cin >> N;
  P.resize(N);
  for (int i = 0; i < N; i++) {
    cin >> P[i].first >> P[i].second;
  }
  // Generate valid circles.
  vector<tuple<int, int, int>> circles;
  for (int Ax = 0; Ax <= BOUNDS; Ax++) {
    for (int Ay = 0; Ay <= BOUNDS; Ay++) {
      int Ar = 1;
      while (Ar <= BOUNDS && !check(Ax, Ay, Ar)) {
        Ar++;
      }
      if (Ar <= BOUNDS) {
        circles.push_back({Ax, Ay, Ar});
      }
    }
  }
  // Try for all valid circles.
  int bestAx = -1, bestAy = -1, bestBx = -1, bestBy = -1, bestR = -1;
  double bestArea = 999999;
  for (int a = 0; a < (int)circles.size(); a++) {
    auto [Ax, Ay, R] = circles[a];
    for (int b = a + 1; b < (int)circles.size(); b++) {
      auto [Bx, By, Br] = circles[b];
      if (R != Br) {
        continue;
      }
      double dsq = distsq(Ax - Bx, Ay - By);
      // Fail if circles don't overlap.
      if (dsq >= 4 * R * R) {
        continue;
      }
      // Choose the answer that minimizes the area of the overlap.
      double d = sqrt(dsq);
      double fouradsq = sqrt((4 * R * R) - dsq);
      double area = R * R * M_PI;
      area -= 2 * R * R * atan2(d, fouradsq);
      area -= 0.5 * d * fouradsq;
      if (area < bestArea) {
        bestArea = area;
        bestAx = Ax;
        bestAy = Ay;
        bestBx = Bx;
        bestBy = By;
        bestR = R;
      }
    }
  }
  // Compute sum of squared distance to points from both A and B.
  // If B's sum is less, B is actually A.
  // Note: We can afford to use all N points for this, no need to sample.
  double Asum = 0, Bsum = 0;
  for (auto [x, y] : P) {
    Asum += distsq(x - bestAx, y - bestAy);
    Bsum += distsq(x - bestBx, y - bestBy);
  }
  if (Bsum < Asum) {
    swap(bestAx, bestBx);
    swap(bestAy, bestBy);
  }
  cout << bestAx << " " << bestAy << " " << bestBx << " " << bestBy << " "
       << bestR << endl;
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  int T;
  cin >> T;
  for (int t = 1; t <= T; t++) {
    cout << "Case #" << t << ": ";
    solve();
  }
  return 0;
}