QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#871486 | #8614. 3D | ucup-team6275# | TL | 6ms | 4096kb | C++23 | 4.1kb | 2025-01-25 20:51:33 | 2025-01-25 20:51:42 |
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));
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() + 0.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]), ypp = pts[i] - (pts[v] - pts[i]).norm(d[v][i]);
if (dist(yp, pts[v]) > dist(ypp, pts[v]))
yp = ypp;
cur = cur + yp * ws[i][v];
normed += ws[i][v];
}
cur = cur * (1 / normed);
pts[v] = cur;
cnt_bad += check(v);
++iters;
if (iters >= 5000) {
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;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
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.13968194353543002652 -0.20265941921736412415 -0.28599323118641048927 0.18648229753183825545 0.14208968617302578148 0.29815849933283650297 -0.24488271001468996769 0.22605587008235153979 -0.13402095813911117177 -0.08128153105257831433 -0.16548613703801319714 0.12185568999268515806
result:
ok OK. Max delta: 0.099756
Test #2:
score: 0
Accepted
time: 0ms
memory: 4096kb
input:
1 0.000000
output:
0.00000000000000000000 0.00000000000000000000 0.00000000000000000000
result:
ok OK. Max delta: 0.000000
Test #3:
score: 0
Accepted
time: 1ms
memory: 3968kb
input:
2 0.000000 0.938096 0.938096 0.000000
output:
-0.15018930607301485334 0.23370399016082128718 -0.37793073919465324523 0.15018930607301485334 -0.23370399016082128715 0.37793073919465324520
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.29115533269598962448 -0.04199119024252837527 0.08354399414445975021 -0.44972077105470511642 0.12078463312319478751 0.15218154548012581887 0.15856543835871549189 -0.07879344288066641208 -0.23572553962458556906
result:
ok OK. Max delta: 0.061692
Test #5:
score: 0
Accepted
time: 0ms
memory: 3968kb
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.15625224240051908855 0.26779913595612105651 0.15278475297953667071 -0.04101548307286822023 -0.18858634659248425358 0.19234901249205118082 -0.03091767837033760751 0.01394771271166361580 0.14775041433367508035 0.27349106023799248729 0.39264021850119764487 -0.03657583543303039546 -0.35781014119530574...
result:
ok OK. Max delta: 0.098934
Test #6:
score: 0
Accepted
time: 0ms
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.13575391622817263270 -0.33953834912862992847 -0.39087616479846863174 -0.46572727668645373683 0.41757072092688084128 -0.10782330074362964773 -0.05557235671799088262 0.30287769105454032700 0.00713735689530809505 0.60204590881260125360 -0.12403027972146418842 0.09733910122602869717 0.271287777212807...
result:
ok OK. Max delta: 0.098804
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.09968041181645816246 0.03262019099279645553 -0.40388409404948149317 0.20482601407435332492 0.48923035264874821813 -0.01530819119273371030 0.08630530695136776531 -0.09881581194376925001 -0.05239871582468420797 -0.39101099560094079307 -0.08437746119907820283 0.27436110896306200387 0.271433438675695...
result:
ok OK. Max delta: 0.097298
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.16243588404047089386 0.16573468265090473514 0.31107275782873977654 -0.07508490128997874350 0.04487606257413355069 -0.10689691548852910992 -0.00911447293119856827 0.01860511811778906461 -0.53148164003666186254 -0.11653598714263061837 0.05649917758591658053 0.24843462115066092700 0.3098112386637143...
result:
ok OK. Max delta: 0.099437
Test #9:
score: 0
Accepted
time: 0ms
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.43762733630002865695 0.11226060363605729753 0.09669357158662856728 0.44436493203354897325 0.32708131646764805112 -0.02624521663645522522 -0.04569773083506068395 -0.14032246184210459019 -0.14167414703809703614 -0.04012263589013065064 0.17897064102623641183 -0.17625324862269394220 0.279486496684315...
result:
ok OK. Max delta: 0.097053
Test #10:
score: 0
Accepted
time: 3ms
memory: 3968kb
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.54960100565253258893 0.03070091412235340512 -0.36539685920623313158 -0.39418664898329215917 0.00153392441660071067 0.26560210185674558575 0.19319204727568932742 -0.07062907473357511016 -0.25264960647575980508 -0.21919604267277514848 0.43736980429982009804 0.18810273303979198114 0.11455515786191501...
result:
ok OK. Max delta: 0.099441
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.13401379452665211148 0.22634113112412776702 -0.03131878112569837252 -0.16463140509817932136 -0.17804054370727354689 0.34586363403592710827 0.01877836973598209593 0.29819416541008954009 -0.32136129623992488021 -0.00344897387855047291 -0.47531476176924761793 -0.04587140604411800768 0.42317917743685...
result:
ok OK. Max delta: 0.099083
Test #12:
score: 0
Accepted
time: 0ms
memory: 4096kb
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.03505674241380788141 -0.23867647883653972598 0.28373365328361549757 -0.39333623355475654185 -0.10409206145100408412 -0.13382521687944791037 -0.34372889310493946874 0.37195282042692498205 -0.45053240670267106794 0.02731122740465525292 0.31677738987477439272 -0.31038918551083839997 0.28596874176161...
result:
ok OK. Max delta: 0.099726
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.46163161069681312489 -0.41366377551804387592 0.08220338672768011189 -0.39289508572275649726 -0.12926834366601480994 0.15191538461954328813 -0.20564055044742753038 0.37745536479803136048 -0.05388737769610967314 -0.15173528545235680645 -0.22284503571235171867 -0.43701985931455992199 0.4296738733365...
result:
ok OK. Max delta: 0.099962
Test #14:
score: 0
Accepted
time: 6ms
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.25515982341401635019 -0.01562896539977010545 -0.15829853773782581885 0.48742815906622562395 0.02980996486493837645 -0.10927110208176617673 0.28593591804841498119 0.57348144791976874183 -0.24301719617814189195 -0.70454721620269251383 -0.04099710363578031055 -0.25366058195878229682 -0.08954575015433...
result:
ok OK. Max delta: 0.097709
Test #15:
score: 0
Accepted
time: 1ms
memory: 4096kb
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.46825448788784769771 -0.02738908046390967077 0.29130377961850914737 0.10506227232733504113 0.24207533891111922693 0.13815279812550793320 -0.34575624531487856697 0.36994883665767489710 0.19720800927727492142 0.43473791231684668067 -0.10857629128742068612 0.13440099971920967136 -0.18226618292584718...
result:
ok OK. Max delta: 0.099526
Test #16:
score: 0
Accepted
time: 0ms
memory: 4096kb
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.25538073655591822547 0.10610057657117501299 0.14888807670640451236 -0.01207848559724152969 -0.45997767450722565463 0.34169504050027965517 -0.33421513567714176846 0.50539882840114764721 -0.37016097352153735822 0.39275100006805802001 0.13397092344709051289 -0.36822120606299682668 0.1280737290088126...
result:
ok OK. Max delta: 0.095590
Test #17:
score: 0
Accepted
time: 0ms
memory: 4096kb
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.43694999844765194195 -0.05201332736027394676 0.15204383125732422730 0.07852403560909405200 -0.44455234685769946771 0.02711868502857635017 -0.30338040061947495397 0.41752968195471255780 -0.30628728978489645093 0.37925660407992029948 -0.04765812053043425880 -0.12406620549192032770 0.222302997015664...
result:
ok OK. Max delta: 0.097179
Test #18:
score: -100
Time Limit Exceeded
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 ...