QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#611824#9289. 1%-EuclideanYzm007WA 654ms11212kbC++141.3kb2024-10-04 22:58:342024-10-04 22:58:35

Judging History

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

  • [2024-11-18 16:44:13]
  • hack成功,自动添加数据
  • (/hack/1194)
  • [2024-10-04 22:58:35]
  • 评测
  • 测评结果:WA
  • 用时:654ms
  • 内存:11212kb
  • [2024-10-04 22:58:34]
  • 提交

answer

// https://codeforces.com/gym/104848/problem/I
#include <bits/stdc++.h>
#define fore(i, a, b) for (ll i = a, gmat = b; i < gmat; i++)
#define FIN ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
using namespace std;
typedef long long ll;
typedef pair<ll, ll> ii;
typedef vector<ll> vi;
typedef vector<ii> vii;

#pragma GCC optimize("Ofast")

double dist(ii p0, ii p1) {
  auto [x0, y0] = p0;
  auto [x1, y1] = p1;

  return sqrt((double)((x1 - x0) * (x1 - x0) + (y1 - y0) * (y1 - y0)));
}

const ll total = 4e7;

double solve(const vii& ps) {
  ll n = ps.size();

  if (n*n <= total) {
    double ans = 0.0;
    fore(i, 0, n) {
      fore(j, i + 1, n) {
        ans += dist(ps[i], ps[j]);
      }
    }
    return ans;
  } else {
    double ans = 0.0;

    static random_device rd;
    static mt19937_64 gen(rd());
    uniform_int_distribution<ll> dis(0, n - 1);

    fore(_, 0, total) {
      ll i = dis(gen), j = dis(gen);

      if (i != j) {
        ans += dist(ps[i], ps[j]);
      }
    }

    ans *= ((double)(n * (n - 1))) / ((double)(2*total));

    return ans;
  }
}

int main() {
  FIN;

  ll n;
  cin >> n;
  vii ps(n);
  for (auto& [x, y] : ps) {
    cin >> x >> y;
  }

  cout << setprecision(5) << fixed;
  cout << solve(ps) << '\n';

  return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

3
-1 2
2 2
-1 -2

output:

12.00000

result:

ok error = 0.00000 (0.00000e+00)

Test #2:

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

input:

4
0 0
2 0
0 2
2 2

output:

13.65685

result:

ok error = -0.00000 (-3.11126e-07)

Test #3:

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

input:

10
-5 -9
5 -1
-8 -7
-6 10
1 -2
-1 -6
-2 3
-3 -1
-5 2
-10 9

output:

447.93601

result:

ok error = -0.00000 (-5.89593e-09)

Test #4:

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

input:

100
38 5
49 98
51 73
-9 88
85 -17
74 -89
-7 -83
75 -45
-7 -86
-1 -83
64 29
-100 70
94 -31
33 -58
-19 53
-68 -24
-20 -95
-58 -82
96 17
-57 -66
25 -82
33 -88
-30 9
-78 -81
-96 80
-61 98
-70 91
18 -75
-74 -57
-49 46
-30 83
33 -71
97 -36
77 -98
-41 -80
-10 -58
-65 -82
75 -56
71 -99
-79 18
-69 45
85 37
1...

output:

568237.01129

result:

ok error = 0.00000 (7.44768e-12)

Test #5:

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

input:

1000
944 590
-334 904
889 -282
425 -325
-103 -809
993 911
143 443
-932 605
-301 -176
-157 146
-633 -399
-150 955
-363 -14
-817 493
-47 720
-928 -965
-8 -316
272 -299
907 -72
-844 758
642 -52
235 498
-822 204
-224 618
337 55
-809 710
-564 -937
-638 -371
-961 244
-652 408
-298 955
264 -680
-963 -767
-...

output:

519539465.95200

result:

ok error = -0.00000 (-1.87003e-14)

Test #6:

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

input:

10000
-659 -2844
-8357 -6691
-1461 -3785
-2767 2416
-8822 1703
9241 -2262
-1504 -3990
6987 -5208
2984 -9116
7244 2503
-6187 6720
-1624 -931
6738 -7167
2962 -4352
-6964 -8792
6241 -582
-6450 -1229
2177 -1269
1714 -3459
-7260 -8263
6329 5496
9797 -8972
927 -5671
-2721 3134
9392 5161
-5527 -2240
-983 7...

output:

520569250754.69495

result:

ok error = -0.00004 (-3.80053e-05)

Test #7:

score: 0
Accepted
time: 529ms
memory: 4748kb

input:

100000
-83701 75196
45765 -6235
36272 37275
-35366 -82843
8306 -1369
-28173 46051
-65089 -8781
75824 -54559
-55700 -93735
59743 86007
-72405 -47645
24812 35094
-4454 -21204
-35485 87381
28200 45650
904 -80565
38488 14842
10353 48050
66074 7042
61753 71952
55030 -92952
-44662 -94767
-59269 -34289
374...

output:

520967330786689.93750

result:

ok error = -0.00003 (-2.73874e-05)

Test #8:

score: 0
Accepted
time: 646ms
memory: 11060kb

input:

500000
-583904 203313
-340892 -796716
910437 -246461
-246636 206026
-735478 953404
746547 -77553
-661769 967977
-312048 -680490
-776092 95714
140302 677488
-907238 962373
-225267 107163
714274 -295282
430205 384021
-737797 -503077
871316 171099
-234497 -767343
-149102 399526
912881 -921105
-831662 6...

output:

130308268473464928.00000

result:

ok error = -0.00024 (-2.40353e-04)

Test #9:

score: 0
Accepted
time: 625ms
memory: 10984kb

input:

500000
3 8
-4 -10
6 7
5 -8
-4 4
2 8
-7 4
-10 -5
-9 -1
-7 9
7 10
3 5
2 -4
-10 -10
3 0
-3 7
-2 -9
8 4
-5 -6
2 -9
10 -4
9 4
3 -2
-6 8
0 8
-5 -9
-3 10
-9 -3
-7 -9
-7 8
-3 1
-1 -8
-9 7
-9 7
-5 0
-1 -1
-3 9
-2 -6
-5 1
7 -4
-4 5
7 5
-8 5
4 -2
6 8
6 6
4 -10
-7 -5
7 10
10 2
9 -4
-3 -6
1 9
-1 -10
-1 9
1 1
-10...

output:

1367083802390.80835

result:

ok error = 0.00009 (8.60471e-05)

Test #10:

score: 0
Accepted
time: 599ms
memory: 10984kb

input:

500000
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0...

output:

0.00000

result:

ok error = 0.00000 (0.00000e+00)

Test #11:

score: 0
Accepted
time: 654ms
memory: 11212kb

input:

500000
-1000000 -1000000
-1000000 -1000000
1000000 1000000
1000000 1000000
-1000000 -1000000
-1000000 -1000000
-1000000 -1000000
1000000 1000000
1000000 1000000
1000000 1000000
1000000 1000000
1000000 1000000
1000000 1000000
-1000000 -1000000
1000000 1000000
-1000000 -1000000
1000000 1000000
1000000...

output:

176715539534579968.00000

result:

ok error = -0.00035 (-3.46032e-04)

Test #12:

score: 0
Accepted
time: 640ms
memory: 10852kb

input:

500000
-70213 -71203
-61054 -79198
-95941 28199
-11770 99304
18752 98225
73256 68069
-88777 46027
-67547 73738
-87962 -47566
48747 87313
32574 94545
93353 -35849
-97310 -23035
92492 38013
-59278 -80535
-27784 -96062
47366 88070
-21221 97722
79500 -60660
-82446 56590
19991 97981
-89590 44424
85179 52...

output:

15922217892349838.00000

result:

ok error = 0.00015 (1.54641e-04)

Test #13:

score: 0
Accepted
time: 634ms
memory: 11136kb

input:

500000
-6858 -7277
2327 -9725
-5846 -8113
-5662 -8242
3573 -9339
-9999 90
-1601 9870
9875 -1571
7589 6511
-5146 -8573
-1281 -9917
4273 -9040
-4928 -8701
6890 -7247
-5057 -8626
9204 3908
6224 7826
-8209 5709
-7024 -7117
5797 8148
2480 9687
-8405 5416
-7298 6835
-4742 -8804
8882 -4594
-9285 3712
-4701...

output:

1596588399281720.50000

result:

ok error = 0.00013 (1.31272e-04)

Test #14:

score: 0
Accepted
time: 635ms
memory: 11072kb

input:

500000
-985 -166
840 -542
-303 -952
-514 -857
-170 985
-888 -458
999 -22
171 985
-997 73
937 347
-474 880
52 -998
482 875
-999 18
-465 -885
-998 54
987 -157
-992 -124
998 48
-826 563
-604 -796
971 238
904 -427
-820 571
935 352
189 981
487 873
-974 -226
987 -155
-72 997
418 -908
192 981
660 -750
881 ...

output:

163941438617034.62500

result:

ok error = -0.00063 (-6.32708e-04)

Test #15:

score: 0
Accepted
time: 636ms
memory: 10948kb

input:

500000
64 -76
39 91
-99 12
99 12
99 -8
96 27
8 -99
-83 -55
93 -35
-36 -93
-7 99
-19 98
49 86
99 -9
99 4
-99 -9
54 -84
68 -72
83 55
-95 30
97 -23
-10 99
99 8
-96 -27
-99 -6
29 -95
15 -98
-87 -49
68 -73
-88 -46
99 -4
-88 -46
40 91
-60 -79
47 -88
-47 88
93 -36
-91 -40
98 19
-31 94
-78 62
27 -96
-80 -59...

output:

20911303911207.81250

result:

ok error = 0.00497 (4.97020e-03)

Test #16:

score: -100
Wrong Answer
time: 626ms
memory: 11072kb

input:

500000
9 -4
8 -5
-9 1
3 -9
3 9
-2 9
-9 3
7 -7
-7 6
5 -8
-9 0
0 -9
0 -9
6 -7
0 9
1 -9
0 -9
9 -3
-1 9
-9 1
0 -9
-9 0
-9 -2
8 5
-5 -8
-9 1
8 -5
-9 -3
-8 4
2 -9
-9 2
-8 -4
2 9
-8 5
-1 -9
-3 -9
4 -9
8 5
-4 8
8 5
4 8
2 -9
-3 9
-3 9
-6 7
0 9
9 -3
9 -3
-8 -5
3 9
-9 0
-1 -9
-7 6
1 9
-7 6
4 8
-6 7
1 9
9 2
-9 ...

output:

6666872784153.89844

result:

wrong answer error = 0.02998 (2.99806e-02)