QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#611824 | #9289. 1%-Euclidean | Yzm007 | WA | 654ms | 11212kb | C++14 | 1.3kb | 2024-10-04 22:58:34 | 2024-10-04 22:58:35 |
Judging History
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)