QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#871517 | #8614. 3D | ucup-team6275# | TL | 727ms | 4096kb | C++23 | 4.2kb | 2025-01-25 20:57:55 | 2025-01-25 20:57:57 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define rep(i, n) for (int i = 0; i < (n); i += 1)
#define len(a) ((int)(a).size())
mt19937_64 rnd(time(0));
mt19937 rndint(time(0) + 10);
const ll inf = 1e18;
const int SZ = 11;
const ld eps = 1e-9;
ld d[SZ][SZ];
int n;
struct pt {
ld x, y, z;
ld ln() {
return sqrtl(x * x + y * y + z * z);
}
pt operator+(const pt &rht) {
return {x + rht.x, y + rht.y, z + rht.z};
}
pt operator-(const pt &rht) {
return {x - rht.x, y - rht.y, z - rht.z};
}
pt operator*(ld fuck) {
return {x * fuck, y * fuck, z * fuck};
}
pt norm(ld a = 1) {
ld nrm = a / ln();
return {x * nrm, y * nrm, z * nrm};
}
};
vector<pt> pts;
ld distsq(const pt &a, const pt &b) {
return (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y) + (a.z - b.z) * (a.z - b.z);
}
ld dist(const pt &a, const pt &b) {
return sqrtl(distsq(a, b));
}
ld get_random_ld() {
const ll mod = 1e15;
return rnd() % mod / (ld)(mod - 1);
}
int check(int v) {
int res = 0;
for (int i = 0; i < n; ++i) {
if (i != v && abs(dist(pts[i], pts[v]) - d[i][v]) > 0.1 - eps)
++res;
}
return res;
}
int32_t main() {
if (1) {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
}
cin >> n;
#ifdef LOCAL
vector<pt> genpts(n);
for (int i = 0; i < n; ++i) {
genpts[i].x = get_random_ld();
genpts[i].y = get_random_ld();
genpts[i].z = get_random_ld();
}
for (int i = 0; i < n; ++i) {
d[i][i] = 0;
for (int j = i + 1; j < n; ++j) {
d[i][j] = dist(genpts[i], genpts[j]) - (get_random_ld() - 0.5) / 5;
d[j][i] = d[i][j];
}
}
#else
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j)
cin >> d[i][j];
}
#endif
while (true) {
pts.resize(n);
vector<vector<ld>> ws(n, vector<ld>(n));
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
ws[i][j] = get_random_ld() + 5;
}
}
for (int i = 0; i < n; ++i) {
pts[i].x = get_random_ld();
pts[i].y = get_random_ld();
pts[i].z = get_random_ld();
}
int cnt_bad = 0;
for (int i = 0; i < n; ++i)
cnt_bad += check(i);
cnt_bad /= 2;
int iters = 0;
bool fail = false;
while (cnt_bad) {
int v = rndint() % n;
cnt_bad -= check(v);
pt cur = {0, 0, 0};
ld normed = 0;
for (int i = 0; i < n; ++i) {
if (i == v)
continue;
pt yp = pts[i] + (pts[v] - pts[i]).norm(d[v][i]);
cur = cur + yp * ws[i][v];
normed += ws[i][v];
}
cur = cur * (1 / normed);
pts[v] = cur;
cnt_bad += check(v);
if (iters % 100 == 0) {
cnt_bad = 0;
for (int i = 0; i < n; ++i) {
cnt_bad += check(i);
}
cnt_bad /= 2;
}
++iters;
if (iters >= 1000) {
fail = true;
break;
}
}
if (fail)
continue;
#ifdef LOCAL
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
cout << setprecision(10) << fixed << dist(pts[i], pts[j]) << " ";
}
cout << "\n";
}
#endif
pt avg = {0, 0, 0};
for (auto c : pts) {
avg = avg + c;
}
avg.x /= n;
avg.y /= n;
avg.z /= n;
for (auto c : pts) {
c = c - avg;
cout << setprecision(20) << fixed << c.x << " " << c.y << " " << c.z << "\n";
}
break;
}
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 4096kb
input:
4 0.000000 0.758400 0.557479 0.379026 0.758400 0.000000 0.516608 0.446312 0.557479 0.516608 0.000000 0.554364 0.379026 0.446312 0.554364 0.000000
output:
-0.21126761838571643079 -0.24668033012071098367 -0.18462825239648039468 0.30040028836334361465 -0.06757935864321174631 0.19525320808034630555 0.12289661901362098565 0.26103201146605989479 -0.14386315353894512178 -0.21202928899124816951 0.05322767729786283513 0.13323819785507921078
result:
ok OK. Max delta: 0.096440
Test #2:
score: 0
Accepted
time: 0ms
memory: 3968kb
input:
1 0.000000
output:
0.00000000000000000000 0.00000000000000000000 0.00000000000000000000
result:
ok OK. Max delta: 0.000000
Test #3:
score: 0
Accepted
time: 0ms
memory: 4096kb
input:
2 0.000000 0.938096 0.938096 0.000000
output:
-0.35517639295870998551 -0.14775305103008373811 0.26837435067483907862 0.35517639295870998551 0.14775305103008373811 -0.26837435067483907868
result:
ok OK. Max delta: 0.000000
Test #4:
score: 0
Accepted
time: 0ms
memory: 3968kb
input:
3 0.000000 0.769195 0.308169 0.769195 0.000000 0.686850 0.308169 0.686850 0.000000
output:
0.27119450154639531531 -0.10938343026065024577 0.07415756027527877953 -0.40259300364111007909 0.08156931876118116572 0.14297382416415282494 0.13139850209471476373 0.02781411149946908003 -0.21713138443943160449
result:
ok OK. Max delta: 0.065499
Test #5:
score: 0
Accepted
time: 0ms
memory: 4096kb
input:
5 0.000000 0.444506 0.292333 0.209539 1.195824 0.444506 0.000000 0.220873 0.748833 0.757486 0.292333 0.220873 0.000000 0.533499 0.797167 0.209539 0.748833 0.533499 0.000000 1.141148 1.195824 0.757486 0.797167 1.141148 0.000000
output:
-0.02107812003268856357 -0.23632320060514163643 0.27124939624073550763 0.24308721899795243322 0.05047953325190399196 -0.05927350693317874245 0.12214881803884560333 0.05648195941027571085 0.14264960167579622546 -0.16603897514988848320 -0.42422240519198750619 0.12933958906002905522 -0.1781189418542209...
result:
ok OK. Max delta: 0.094386
Test #6:
score: 0
Accepted
time: 1ms
memory: 4096kb
input:
6 0.000000 0.932377 0.787009 0.996894 0.763544 0.651377 0.932377 0.000000 0.421278 1.155673 1.149686 0.508563 0.787009 0.421278 0.000000 0.709021 0.793974 0.224884 0.996894 1.155673 0.709021 0.000000 0.392548 0.957498 0.763544 1.149686 0.793974 0.392548 0.000000 0.714079 0.651377 0.508563 0.224884 0...
output:
-0.07611094945340264953 -0.56506879778267305624 0.00898709626233315810 -0.45697377386516848503 0.23965624006878236875 0.36378990461425489010 -0.12746254045813023100 0.16235199082715613133 0.14965929986450246411 0.21859893006593720518 0.09670202464272677936 -0.57354243163802988117 0.44416992447470650...
result:
ok OK. Max delta: 0.098227
Test #7:
score: 0
Accepted
time: 1ms
memory: 4096kb
input:
7 0.000000 0.688481 0.455407 0.777049 0.963980 0.255052 0.554599 0.688481 0.000000 0.596921 0.827787 1.260207 0.340235 0.493011 0.455407 0.596921 0.000000 0.609173 0.640567 0.352193 0.243913 0.777049 0.827787 0.609173 0.000000 0.858134 0.701131 0.393303 0.963980 1.260207 0.640567 0.858134 0.000000 0...
output:
0.36705444719796921724 0.13793903614067928821 0.14398058962402837110 -0.03779996358638968820 0.50207454153717302715 -0.18285620707426438687 0.04742658879053675001 -0.08585695618962943949 0.07482178110131979264 -0.24850511821585307143 -0.25495746114949181918 -0.34132561242467449736 -0.222343262142092...
result:
ok OK. Max delta: 0.099765
Test #8:
score: 0
Accepted
time: 1ms
memory: 3968kb
input:
8 0.000000 0.437494 0.934265 0.074097 0.673669 0.425700 0.479212 0.679270 0.437494 0.000000 0.331045 0.393801 0.527073 0.402792 0.375134 0.461133 0.934265 0.331045 0.000000 0.792317 0.605663 0.880433 0.786178 0.455534 0.074097 0.393801 0.792317 0.000000 0.681633 0.278020 0.327267 0.550058 0.673669 0...
output:
-0.02356625537331869902 0.31917471214501465384 -0.20695456694404957250 0.11088896265454297840 -0.11113391269243923199 0.07672371291194869945 0.01093913067342079445 -0.50431049564127995006 0.20755430993955044025 -0.02055782141448536554 0.26108181282733711166 -0.09327060070367540023 -0.024018398486281...
result:
ok OK. Max delta: 0.097878
Test #9:
score: 0
Accepted
time: 1ms
memory: 4096kb
input:
9 0.000000 0.883128 0.449200 0.525234 0.745161 0.323207 0.430759 1.247103 0.564870 0.883128 0.000000 0.664206 0.590150 0.433578 0.890708 0.741718 0.798316 1.033522 0.449200 0.664206 0.000000 0.326949 0.636800 0.523900 0.642051 0.680925 0.349474 0.525234 0.590150 0.326949 0.000000 0.523965 0.344241 0...
output:
0.41316053967549293984 0.04031754339893239847 0.18096415337597600043 -0.14066311534566615393 -0.27999019913892627331 -0.45215725654912217052 -0.09547069298390835156 -0.03981619189565881089 0.18816684391694357372 0.05732753313986417435 -0.25918077860714344111 0.03776509923367037379 -0.015645715203589...
result:
ok OK. Max delta: 0.099508
Test #10:
score: 0
Accepted
time: 0ms
memory: 4096kb
input:
10 0.000000 1.141963 0.357381 0.960442 0.887799 0.393165 1.000015 0.883861 1.059968 0.666258 1.141963 0.000000 0.730979 0.430440 0.528721 0.822481 0.567380 0.334929 0.552413 0.840500 0.357381 0.730979 0.000000 0.861027 0.623726 0.216981 0.719423 0.558824 0.726378 0.310217 0.960442 0.430440 0.861027 ...
output:
-0.34210156900188326925 0.23330099120059545137 0.51751661204675004956 0.10737317057748168122 -0.32101888231310154049 -0.30470999374912206787 -0.11254055969425943412 0.04526182848308471155 0.29966730274099133907 -0.20098106703564218694 -0.06544810346862677976 -0.48668970855755098418 0.186982071129478...
result:
ok OK. Max delta: 0.096722
Test #11:
score: 0
Accepted
time: 0ms
memory: 4096kb
input:
10 0.000000 0.508467 0.359704 0.705660 0.752608 0.632298 0.433047 0.541855 0.108842 0.652503 0.508467 0.000000 0.849608 0.542157 0.614068 0.673963 0.552462 0.470005 0.697815 0.822930 0.359704 0.849608 0.000000 0.832286 0.790254 0.844729 0.428335 0.707356 0.221649 0.447522 0.705660 0.542157 0.832286 ...
output:
-0.02034643106395315430 -0.12173515872935126419 0.23463247004707799177 -0.35239712348892386878 -0.11783143979931450388 -0.21622986979131841707 0.28689964937716614477 0.00003330387558297664 0.33680722902482993164 0.08902879725826535473 -0.05411181022428438670 -0.46379795921400445487 -0.00586431749869...
result:
ok OK. Max delta: 0.098777
Test #12:
score: 0
Accepted
time: 1ms
memory: 3968kb
input:
10 0.000000 0.532841 1.081715 0.791902 0.304710 0.943952 0.318604 0.512618 0.263399 0.317304 0.532841 0.000000 0.617254 0.571776 0.863445 0.644868 0.534570 0.898453 0.767957 0.380512 1.081715 0.617254 0.000000 0.498716 1.118400 0.375946 0.739541 1.081104 0.985516 0.778030 0.791902 0.571776 0.498716 ...
output:
0.27577981706892396908 -0.16702498601302091598 0.20277605454415494464 -0.20774779991558635063 -0.38750259775219361084 -0.01744730787357015277 -0.62246288606333283720 0.05930048803166623164 -0.23040681709668597410 -0.14084700651521285980 -0.03298448401498655221 -0.44158032435290848854 0.3472958388835...
result:
ok OK. Max delta: 0.099756
Test #13:
score: 0
Accepted
time: 0ms
memory: 4096kb
input:
10 0.000000 0.337812 0.820740 0.714576 0.958294 1.114603 1.052855 0.816204 0.921684 0.581533 0.337812 0.000000 0.588126 0.550959 0.851936 1.076003 0.824637 0.634512 0.630209 0.781504 0.820740 0.588126 0.000000 0.754545 0.853344 0.651402 0.625435 0.521290 0.463145 0.927492 0.714576 0.550959 0.754545 ...
output:
0.29544379105598429598 -0.50474093567428691048 0.20082764537560410457 0.34101151605641770098 -0.19233215100408415093 0.22973801005100370092 0.29349032058860071627 0.31468065177293534450 -0.04659154282439631844 0.18592973829174255131 -0.28511817156737898497 -0.39462054828278294414 -0.4756095482218014...
result:
ok OK. Max delta: 0.099028
Test #14:
score: 0
Accepted
time: 25ms
memory: 3968kb
input:
10 0.000000 0.157221 0.630350 0.940948 0.790907 0.666502 0.536584 0.506196 0.353744 0.642539 0.157221 0.000000 0.582092 1.279081 0.812532 0.810677 0.850103 0.865478 0.320962 0.694578 0.630350 0.582092 0.000000 1.171965 1.045437 1.168568 0.582206 0.854963 0.513105 1.137099 0.940948 1.279081 1.171965 ...
output:
-0.21840823025948368875 -0.10597794012929977867 -0.20828024699762060661 -0.19077999979225371873 -0.24764280104794303789 -0.41356208561433037391 -0.07228319426552676883 -0.66978299169420936720 0.04735291391169192866 -0.16876400684630345179 0.31744221411357191116 0.64886862412934458215 0.4690195452021...
result:
ok OK. Max delta: 0.099444
Test #15:
score: 0
Accepted
time: 1ms
memory: 3968kb
input:
10 0.000000 0.655953 0.416075 0.956128 0.351321 0.411663 0.904277 0.786858 0.961004 1.159073 0.655953 0.000000 0.398507 0.430374 0.378366 0.531641 0.789955 0.396050 0.368849 1.088933 0.416075 0.398507 0.000000 0.976294 0.461240 0.328488 0.979923 0.705916 0.884932 1.254989 0.956128 0.430374 0.976294 ...
output:
-0.30007473824725849323 0.04646004535186344431 0.47163829572563385084 0.09038230902024393826 0.20577950280993771438 0.08974553400512683132 -0.37719028536794795833 0.34078516749745139323 0.18305012278809553150 0.40287363281746386271 0.15472616334235234390 -0.18823684229582538681 -0.153873617106195878...
result:
ok OK. Max delta: 0.097029
Test #16:
score: 0
Accepted
time: 1ms
memory: 3968kb
input:
10 0.000000 0.672245 0.576475 0.810904 0.599396 0.493165 0.431514 0.511677 0.859634 0.881368 0.672245 0.000000 1.249406 1.027657 0.113558 0.392208 0.862698 0.329856 1.012059 1.039747 0.576475 1.249406 0.000000 0.869439 1.254676 1.087547 0.535956 1.182094 0.744887 0.645939 0.810904 1.027657 0.869439 ...
output:
0.01124475408997140406 0.33885769208809611474 0.04826186831000619707 -0.39963026781255688410 -0.02627496993258351409 0.40249926110104720201 0.19557422892901656959 0.32883911687634083894 -0.59873099539267403754 0.35325458483067650713 -0.38869024763173185615 -0.19817927448547457048 -0.4466597890457711...
result:
ok OK. Max delta: 0.099713
Test #17:
score: 0
Accepted
time: 1ms
memory: 3968kb
input:
10 0.000000 0.609276 0.612588 0.898616 0.668529 0.802163 0.126104 0.681054 0.761434 0.310892 0.609276 0.000000 0.922363 0.423227 0.591390 0.662160 0.751720 0.241917 0.563127 0.693959 0.612588 0.922363 0.000000 0.873479 0.681583 0.707351 0.595097 0.923846 0.768951 0.393683 0.898616 0.423227 0.873479 ...
output:
-0.07142751284437847732 -0.47216830835830451781 0.03780070922968332107 -0.01999387640348773709 0.04037713154417376678 -0.44628266926900576179 -0.45960873573070100442 -0.04273271957755318701 0.34157143418366540819 0.13794415234688316141 0.36147358751935233020 -0.16034678300200623844 0.170234043994708...
result:
ok OK. Max delta: 0.097608
Test #18:
score: 0
Accepted
time: 727ms
memory: 3968kb
input:
10 0.000000 0.542508 0.426558 0.741404 0.733105 0.586307 0.271270 0.847645 0.757695 0.830800 0.542508 0.000000 0.497136 1.012191 1.083431 0.944439 0.618287 0.696705 0.472089 0.354373 0.426558 0.497136 0.000000 0.973354 0.928175 0.884683 0.594828 0.699473 0.534409 0.737409 0.741404 1.012191 0.973354 ...
output:
-0.16783028147341842365 -0.17752101674345832755 -0.25609470430474157762 0.25864528382853196691 0.10248060183716994925 -0.39292264736983636346 0.34456667341273978817 -0.26329436685501684447 -0.18041545482174100524 -0.27452752324826621298 0.37893504893519145782 0.33120126393091275680 -0.30964501511799...
result:
ok OK. Max delta: 0.099459
Test #19:
score: -100
Time Limit Exceeded
input:
10 0.000000 1.061016 0.689894 0.927767 0.698893 0.765947 0.661068 0.306274 0.338125 0.696899 1.061016 0.000000 0.648243 1.014484 1.091752 0.749377 0.935557 1.183802 0.696073 0.582378 0.689894 0.648243 0.000000 0.480864 0.914770 0.542060 0.834022 0.683526 0.147432 0.385821 0.927767 1.014484 0.480864 ...