QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#871411 | #8614. 3D | ucup-team6275# | TL | 1259ms | 4096kb | C++23 | 3.3kb | 2025-01-25 20:39:27 | 2025-01-25 20:39:32 |
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(234);
mt19937 rndint(234);
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 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;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j)
cin >> d[i][j];
}
while (true) {
pts.resize(n);
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};
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;
}
cur.x /= (n - 1);
cur.y /= (n - 1);
cur.z /= (n - 1);
pts[v] = cur;
cnt_bad += check(v);
++iters;
if (iters >= 100000) {
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: 3968kb
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:
1.15307959483087745737 0.62307451581593972361 0.92406772938396565260 1.05735198076037971047 0.87435548842452188122 1.58136645465385452776 0.67216562082187150391 0.58855011932570763409 1.19683408911167219065 1.00456657464479128081 0.94992815953660839079 1.15128846869374271578
result:
ok OK. Max delta: 0.098143
Test #2:
score: 0
Accepted
time: 0ms
memory: 4096kb
input:
1 0.000000
output:
1.90504482321495590509 0.66869392477264066871 1.24617007957988924619
result:
ok OK. Max delta: 0.000000
Test #3:
score: 0
Accepted
time: 1ms
memory: 4096kb
input:
2 0.000000 0.938096 0.938096 0.000000
output:
2.06874554639835258035 0.40561106920842488383 0.79249499952167223442 1.78922384341982129317 0.85482941340217301422 1.56715273169750804786
result:
ok OK. Max delta: 0.000000
Test #4:
score: 0
Accepted
time: 1ms
memory: 3968kb
input:
3 0.000000 0.769195 0.308169 0.769195 0.000000 0.686850 0.308169 0.686850 0.000000
output:
1.32498090539534063288 0.61840207610696400475 1.18424883747104133631 1.19020079923717807073 0.96872555474313182657 1.78499069902584740961 0.98037145692556006030 0.64258309850979101292 1.23931948446779165943
result:
ok OK. Max delta: 0.060829
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.44761133206083027593 0.63496239283144822221 1.45997329889188484544 0.83793683296078248860 0.68421149986606883851 1.15711631089442675241 0.64755900825460026976 0.58038804667231055147 1.17487431847167401251 0.17542233140128414727 0.68570323559406040170 1.37960701591963550957 0.62445860136751548747 0...
result:
ok OK. Max delta: 0.090733
Test #6:
score: 0
Accepted
time: 0ms
memory: 3968kb
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:
1.52349133688219129130 0.60280121722727927566 0.91988840214820922364 1.15264146970194019455 0.80519496488813294176 1.71510722784284200411 0.95116258497176370951 0.55391158151962286273 1.39489160580437148666 0.43908495065369073897 0.61218734619662412482 0.87044850071073182968 0.75467103081269102164 0...
result:
ok OK. Max delta: 0.088679
Test #7:
score: 0
Accepted
time: 0ms
memory: 3968kb
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:
1.51477562248413076974 0.62572471582336399495 0.93155406600183195999 1.38677696081091603154 0.77488213620325721982 1.49715311617919379365 1.11618936173942043494 0.48105435700741435164 0.98873826147814563919 0.70996907060149914135 0.59006459630724109413 1.27689114420356135730 0.73853523579885534968 0...
result:
ok OK. Max delta: 0.099446
Test #8:
score: 0
Accepted
time: 0ms
memory: 4096kb
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:
1.66638153351744969905 0.60581667083979100392 0.93538295655838618999 1.15709254658703059016 0.56031150691722496934 0.99590675140620939709 0.77686771673064692256 0.71539296855564448336 0.88591894991893233025 1.56957389816527873418 0.58882701952808580198 0.99952712928886251059 1.12799978793675219856 0...
result:
ok OK. Max delta: 0.098476
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:
1.47244191957058334652 0.43769005102478859072 1.42705998736615285397 0.64842032026977694899 0.41494828391244184448 0.99486425926774115294 1.27667093288140373998 0.71367055726428644500 1.05552197881707178072 1.24140087578636967435 0.37778346179555575922 1.01144261492736506792 0.76373137667699345213 0...
result:
ok OK. Max delta: 0.097044
Test #10:
score: 0
Accepted
time: 1ms
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:
1.82908967641703804139 0.57415452003318641263 0.71742929703713789454 0.93538391981805903022 0.60608408736602770389 1.40009791712192942616 1.53022898345816983146 0.71648814874558297458 0.91725198825146306064 1.05415873117364906528 0.17002914060282777760 1.26941856795769801667 0.93910398788973946350 0...
result:
ok OK. Max delta: 0.098654
Test #11:
score: 0
Accepted
time: 1ms
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:
1.59944935002721963632 0.53688506714487702016 1.01097173213084667821 1.23483685657999567602 0.11313155614997313937 1.04322004632023167205 1.60369538913764132977 0.87812073666035974658 0.97542093851769617364 0.92779795664931521005 0.48280938070906083469 1.20236634778602583722 0.91125894234371291686 0...
result:
ok OK. Max delta: 0.099438
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:
1.52473567405580944564 0.75545684192472171937 1.10226849498264325945 1.12142017872638236650 0.68706483856714919240 1.51618487330676256816 0.57032718656141999315 0.39658197462636622104 1.27506919429908838844 0.99275333610707265457 0.24557664220262571299 1.29727918257511433083 1.47831012579780148833 0...
result:
ok OK. Max delta: 0.099311
Test #13:
score: 0
Accepted
time: 35ms
memory: 3968kb
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.67712988444793763363 1.05025638422823356635 0.43158681277948274366 0.52688165800104201766 1.16712757696910583586 0.72687989677051744017 0.68474004414700100172 1.42631008848352636685 1.24247442639721680899 1.02556070678065649625 1.50182770669876701833 0.66160875257678840159 0.97360114160128851117 0...
result:
ok OK. Max delta: 0.099571
Test #14:
score: 0
Accepted
time: 1259ms
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.77961740870957948156 0.92072534809631829218 0.91328985587952882534 0.53386280154471049708 0.95940647937793059781 0.84963683842153810914 0.64458124886785916950 0.41950313005579882943 1.08539671594385649968 1.67517098419841987478 0.53643007838145686161 0.64986622741687126285 1.14345784284478057559 1...
result:
ok OK. Max delta: 0.099573
Test #15:
score: 0
Accepted
time: 0ms
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:
1.18874657172400391056 0.33434755054257494928 0.59810381363629757951 0.90069053049409248513 0.69268493083653532026 1.06398390580063639441 0.97569695866366774905 0.25646702556051445356 0.94037879286132563926 0.90314882516217217048 1.15315514192078718138 0.96576902847152915619 1.19679486613521112511 0...
result:
ok OK. Max delta: 0.098840
Test #16:
score: 0
Accepted
time: 1ms
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:
1.37730056483439533793 0.27643699670394697676 1.07309016102083733615 1.49398379629431321135 0.32667397138258013540 0.47114809147385900527 0.88642794986303551536 0.51374376419447263125 1.45670402374677322819 1.39680104929518572512 1.11486676805538482819 1.15706105937222953185 1.44216349259592379467 0...
result:
ok OK. Max delta: 0.099368
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:
1.55689863510157056666 0.63239430253483002153 1.19106448328230643931 1.14579580114668586933 1.17562051304574353853 1.10917514786398956983 1.10346194640456589354 0.28585969878651893214 1.18771974317906711509 0.89106202115644352925 1.01607990111151304182 0.76008717985717370614 1.09155215641610188156 0...
result:
ok OK. Max delta: 0.092585
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 ...