QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#792628#8946. 一眼丁真yyyyxh#40 416ms6400kbC++201.8kb2024-11-29 12:06:322024-11-29 12:06:33

Judging History

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

  • [2024-11-29 12:06:33]
  • 评测
  • 测评结果:40
  • 用时:416ms
  • 内存:6400kb
  • [2024-11-29 12:06:32]
  • 提交

answer

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <random>
using namespace std;
mt19937 rng(random_device{}());
const long double PI = acosl(-1);
const int T = 1000000;
const long double EPS = 0.01;
long double x, y;
void gen(int k) {
    long double ang = 2.0 * PI / k;
    int t = uniform_int_distribution<int>(0, k - 1)(rng);
    long double ax = cosl(ang * t), ay = sinl(ang * t);
    long double bx = cosl(ang * (t + 1)), by = sinl(ang * (t + 1));
    long double rate = uniform_real_distribution<long double>(0, 1)(rng);
    x = ax * rate + bx * (1 - rate);
    y = ay * rate + by * (1 - rate);
}
long double sum[33];
long double X[100000], Y[100000];
const int S = 3000;
int main() {
    for (int k = 3; k <= 30; ++k) {
        for (int i = 0; i < S; ++i)
            gen(k), X[i] = x, Y[i] = y;
        for (int u = 0; u < S; ++u)
            for (int v = u + 1; v < S; ++v)
                sum[k] += (X[u] - X[v]) * (X[u] - X[v]) +
                          (Y[u] - Y[v]) * (Y[u] - Y[v]);
        sum[k] /= S * (S - 1) >> 1;
    }
    int tc;
    scanf("%d", &tc);
    while (tc--) {
        int n, mx;
        scanf("%d%d", &n, &mx);
        for (int i = 0; i < n; ++i)
            scanf("%Lf%Lf", X + i, Y + i);
        long double now = 0;
        for (int u = 0; u < n; ++u)
            for (int v = u + 1; v < n; ++v)
                now += (X[u] - X[v]) * (X[u] - X[v]) +
                       (Y[u] - Y[v]) * (Y[u] - Y[v]);
        now /= n * (n - 1) >> 1;
        int w = 3;
        long double mn = 1e18;
        for (int k = max(mx - 5, 3); k <= mx; ++k) {
            long double dlt = abs(sum[k] - now);
            if (dlt < mn)
                mn = dlt, w = k;
        }
        printf("%d\n", w);
    }
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Pretests


Final Tests

Test #1:

score: 10
Accepted
time: 410ms
memory: 4352kb

input:

200
1000 4
-1.65882 -0.468078
-0.559879 0.302541
-1.67025 -0.452322
-0.54312 -1.40252
0.116365 -0.958391
-1.57137 -0.386501
-1.20353 -0.13415
0.123479 -0.934878
-0.597084 -1.41011
-1.69629 -0.489381
-0.0114821 -1.03665
-0.546439 -1.39593
-0.573469 -1.41618
-1.06124 -1.4763
-1.52521 -0.371347
-1.4609...

output:

4
4
3
4
4
3
3
4
4
3
4
4
4
3
4
4
3
4
4
4
4
3
4
3
4
3
3
3
4
3
3
3
3
3
3
3
3
3
4
3
3
4
3
4
3
3
3
3
4
3
3
3
3
4
3
4
3
3
4
4
3
4
3
4
3
4
4
3
3
3
4
3
3
3
4
4
3
3
3
3
4
4
3
3
3
4
3
3
3
3
4
3
4
3
3
3
4
3
3
4
3
3
4
3
4
4
3
3
4
4
3
4
3
4
4
4
3
4
3
4
3
3
3
3
4
3
4
3
3
3
3
3
3
3
4
4
4
3
4
4
3
4
4
4
4
3
3
3
3
3
...

result:

ok #(wrong) = 0, #(correct) = 200

Test #2:

score: 10
Accepted
time: 411ms
memory: 4232kb

input:

200
1000 4
0.22827 0.536959
-0.743134 0.215561
-0.0821736 -0.804273
0.470104 -0.194576
0.819679 0.553173
0.212657 0.515942
-0.379762 -0.349824
0.140334 -0.864474
-0.033494 0.513621
0.673108 0.243877
0.716308 0.318053
-0.108843 -0.719375
0.102132 -0.924612
0.0141018 -0.921927
0.710421 0.53719
-0.4572...

output:

3
4
3
4
3
3
3
3
4
3
4
4
4
4
4
4
4
3
4
4
3
3
3
4
4
4
4
4
3
3
3
4
4
4
4
4
3
3
3
4
4
4
3
3
4
4
3
4
3
4
3
4
3
3
4
4
3
3
3
4
4
3
4
4
4
4
3
3
3
3
3
3
4
4
3
4
4
4
4
4
3
3
3
4
3
4
3
3
3
3
3
3
3
3
4
4
4
4
4
3
3
3
3
4
3
4
4
3
3
3
4
4
3
4
3
3
4
3
4
3
4
3
4
4
3
4
4
4
3
3
3
3
3
4
4
3
4
4
3
4
4
4
4
4
3
4
3
3
4
3
...

result:

ok #(wrong) = 0, #(correct) = 200

Test #3:

score: 10
Accepted
time: 407ms
memory: 4412kb

input:

200
1000 10
0.171063 0.768938
0.339764 0.873943
1.15161 0.672578
0.805594 0.765797
1.15695 0.666805
1.26595 -0.695135
1.20927 0.578729
-0.356686 -0.292753
0.940372 -0.919379
-0.269337 -0.62435
-0.0757841 0.550908
1.52432 0.00176461
-0.366525 0.00974288
0.524328 0.851771
1.37215 0.224858
0.655827 -0....

output:

7
10
7
5
6
8
10
6
8
10
9
5
9
6
10
7
7
5
10
6
10
7
7
10
7
8
8
7
7
7
10
8
6
8
5
7
9
7
5
10
10
7
5
8
6
8
10
8
8
5
7
10
5
8
8
7
5
6
8
10
7
7
6
6
10
8
10
8
5
9
6
6
9
10
6
9
6
5
5
9
7
8
8
7
7
5
5
7
7
8
6
8
10
6
6
6
7
7
8
7
8
8
8
8
8
6
6
9
5
6
10
5
5
5
10
10
10
10
6
10
8
6
9
9
9
6
6
7
9
10
8
8
7
7
6
10
10
...

result:

ok #(wrong) = 0, #(correct) = 200

Test #4:

score: 10
Accepted
time: 407ms
memory: 6288kb

input:

200
1000 10
-0.83557 -0.43386
-0.900052 0.302486
0.843787 0.446154
-0.0854311 -0.918758
0.501433 0.844022
-0.955344 -0.173521
0.516729 0.8388
-0.917289 0.0698801
-0.925852 0.0681056
-0.848415 0.471305
0.098655 0.922883
0.958545 0.273256
0.67931 0.611085
-0.951816 -0.0694206
-0.245102 0.947475
0.9397...

output:

8
10
10
6
7
9
7
9
10
8
6
5
10
7
9
8
6
10
8
7
8
5
6
8
6
7
5
7
9
6
5
9
7
5
7
5
10
6
6
6
8
8
10
9
8
5
8
6
9
10
7
7
10
9
9
8
9
7
8
5
5
7
6
6
6
8
5
6
9
6
6
8
9
10
5
6
7
8
8
6
10
8
8
10
10
6
10
9
5
7
5
9
6
7
7
6
5
5
10
7
8
9
6
7
5
5
9
8
7
10
6
9
5
9
10
10
6
9
5
9
10
6
8
9
8
10
6
9
5
10
9
8
5
6
7
7
10
9
5
...

result:

ok #(wrong) = 0, #(correct) = 200

Test #5:

score: 0
Wrong Answer
time: 412ms
memory: 4332kb

input:

200
1000 20
1.10645 1.72762
0.00828014 0.0575131
-0.300448 0.537454
0.138879 1.67906
0.73884 1.83804
-0.331532 1.01263
1.57294 1.17098
1.61097 0.722726
0.267742 1.7481
0.805786 -0.115483
1.63489 0.918378
0.358705 -0.0984941
-0.303133 1.14962
1.59952 1.0805
-0.22276 1.35792
1.06748 1.74928
1.48122 1....

output:

20
18
20
17
19
16
20
19
16
15
15
18
16
16
19
20
19
16
19
19
15
20
20
18
16
15
16
19
15
18
20
18
20
18
20
16
20
17
17
16
17
20
18
15
19
19
20
15
16
17
17
18
18
20
16
16
17
18
18
16
20
17
16
18
18
20
18
16
15
17
18
16
19
15
19
15
15
16
19
20
17
20
16
16
17
16
15
15
16
15
18
17
17
15
19
17
15
18
20
15
...

result:

wrong answer #(wrong) = 54, #(correct) = 146

Test #6:

score: 0
Wrong Answer
time: 415ms
memory: 6248kb

input:

200
1000 20
0.306231 0.947555
-0.470695 -0.867584
0.0798229 -0.979712
0.972425 -0.18076
0.205552 0.977367
0.503871 -0.843521
0.931879 -0.34759
-0.528287 -0.821234
0.384399 0.889843
0.0427201 -0.995252
0.911209 0.407903
-0.925169 0.281163
1.01054 0.00777535
0.829844 0.506267
0.145597 -0.98502
-0.2980...

output:

19
20
18
15
19
16
15
16
19
16
17
20
20
15
20
19
19
20
19
16
20
18
18
16
20
15
18
16
16
17
17
18
19
15
19
20
16
15
20
17
20
16
15
17
20
15
15
20
16
20
17
18
20
18
18
16
19
19
15
19
15
18
17
15
15
20
20
20
16
19
20
20
17
17
15
15
20
18
16
20
19
20
19
20
15
19
16
19
18
18
20
18
19
20
20
20
20
15
20
20
...

result:

wrong answer #(wrong) = 53, #(correct) = 147

Test #7:

score: 0
Wrong Answer
time: 416ms
memory: 6400kb

input:

200
1000 25
-0.150207 0.698438
0.0893216 1.09445
1.69859 -0.01418
0.00876932 1.00054
-0.0563829 0.902229
0.736602 1.41841
-0.147213 0.274848
-0.182403 0.345741
1.63542 -0.149404
1.80616 0.580086
1.56376 -0.247799
0.32449 1.26092
0.627195 1.41568
-0.0382449 -0.105866
0.129226 1.13973
0.0847462 -0.261...

output:

23
21
25
23
21
24
21
23
23
21
22
24
20
24
23
23
25
22
25
24
21
21
24
23
22
22
20
22
23
24
23
25
21
23
23
23
21
25
20
21
22
23
25
20
21
21
25
25
25
22
20
24
21
25
22
23
23
25
20
25
25
23
25
25
22
23
25
21
22
22
23
23
25
21
23
21
20
25
25
23
20
20
20
21
23
25
21
24
20
25
25
25
25
22
25
21
25
20
20
21
...

result:

wrong answer #(wrong) = 107, #(correct) = 93

Test #8:

score: 0
Wrong Answer
time: 413ms
memory: 6232kb

input:

200
1000 25
0.964683 -0.212993
0.98252 -0.136339
-0.168828 -0.971035
0.865174 -0.484339
0.571258 -0.82591
-0.797776 -0.589278
-0.307998 -0.948622
-0.80831 0.593024
-0.659663 0.745975
0.923635 -0.380449
0.996853 -0.0380425
0.679349 0.732259
-0.0225609 1.00911
0.717309 -0.710159
-0.425272 -0.901905
0....

output:

22
25
25
25
25
25
25
25
22
23
23
25
24
22
20
25
21
25
21
23
23
22
23
23
22
25
25
25
22
23
22
25
21
25
21
21
21
23
20
23
20
24
23
20
25
23
23
20
23
20
24
22
20
24
25
20
25
22
24
23
24
24
22
21
20
25
25
21
20
25
25
20
20
21
23
24
23
22
24
25
24
25
23
24
25
24
25
20
25
23
25
20
20
25
25
22
22
25
23
21
...

result:

wrong answer #(wrong) = 118, #(correct) = 82

Test #9:

score: 0
Wrong Answer
time: 408ms
memory: 6352kb

input:

200
1000 30
-0.823086 -1.0434
0.105428 -0.15483
-0.502513 -0.953264
0.0771079 -0.121858
-1.23449 0.876862
-0.0812511 -0.664993
-0.241982 0.678029
-0.622296 0.896641
-1.20049 0.882673
-1.88268 -0.190726
0.0489134 -0.354098
0.0159866 -0.415372
-0.167045 -0.751293
-0.0637444 -0.612609
0.0696068 -0.3288...

output:

26
30
30
28
28
27
29
30
30
29
30
25
29
29
28
30
29
30
28
30
26
30
25
30
30
29
30
30
27
28
29
25
30
26
30
30
30
30
29
30
25
30
30
25
30
26
30
29
25
29
26
29
25
30
29
26
25
30
29
30
30
30
29
25
29
27
27
25
26
30
27
26
30
29
30
28
29
29
29
30
30
30
26
30
29
30
29
30
29
29
28
30
29
26
29
29
30
29
30
29
...

result:

wrong answer #(wrong) = 146, #(correct) = 54

Test #10:

score: 0
Wrong Answer
time: 410ms
memory: 4236kb

input:

200
1000 30
-0.922656 0.353773
0.603763 -0.788179
-0.461439 0.857645
-0.991954 -0.0838754
-0.144937 0.982998
0.605566 -0.771346
0.0629471 0.988433
0.995332 -0.0164629
-0.878948 0.473977
-0.852896 0.501311
0.840425 0.516425
0.440577 0.898323
-0.515795 0.861164
0.116181 -1.00427
-0.477573 -0.879226
0....

output:

25
29
30
29
25
25
25
26
29
25
26
25
29
30
30
29
29
27
26
26
27
26
28
29
29
30
29
29
26
30
26
29
26
29
25
29
30
25
29
25
25
29
28
25
29
30
26
29
29
29
26
26
28
29
25
27
29
25
29
29
25
25
25
29
29
27
28
25
29
30
27
29
29
30
29
29
25
25
26
26
27
25
25
29
25
26
28
27
25
25
25
25
29
29
26
29
25
29
29
26
...

result:

wrong answer #(wrong) = 130, #(correct) = 70