QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#871451 | #8614. 3D | ucup-team6275# | TL | 7ms | 4096kb | C++23 | 3.6kb | 2025-01-25 20:45:36 | 2025-01-25 20:46:10 |
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 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;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j)
cin >> d[i][j];
}
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;
}
详细
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.77397553398667076076 0.72380468864136182584 1.87926170747147707840 0.16904871603044445321 1.10282467439847048287 1.88606643004627473528 0.30957787837398679820 0.54133937447621975538 1.73379825737681966986 0.58257743997664281896 1.04235557921123660999 1.78281410323920337820
result:
ok OK. Max delta: 0.081890
Test #2:
score: 0
Accepted
time: 0ms
memory: 4096kb
input:
1 0.000000
output:
0.66869392477264066871 1.24617007957988924619 1.64946299193055564947
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:
1.19188022685328850960 2.13605481483689965509 0.39721014426560226311 0.70439711027596847693 1.34885643646776585513 0.24653489957999020184
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.61989656919177479107 0.49131880904189847585 1.00072237715968162303 0.81225034710557382348 0.35808234299362195046 0.27205951432606064524 0.99946065381680866273 0.42501788611627389704 0.91845747260012845087
result:
ok OK. Max delta: 0.085826
Test #5:
score: 0
Accepted
time: 1ms
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:
1.77384376345180201976 0.72835936054981032222 0.79599067735180597508 1.33822475945657744473 0.94454592039144733917 0.89368705371397199277 1.39597964977337041389 0.76333259077971407679 0.81708509476954962298 1.77895331555413767995 0.57544244222429050015 0.52852891826615186287 0.95806066322616643477 1...
result:
ok OK. Max delta: 0.098593
Test #6:
score: 0
Accepted
time: 1ms
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:
0.31646386563580787557 1.05879760154928637670 1.33314768209895826313 0.48152292374406754639 0.28059099666356405518 0.78739551561114407008 0.80603813431370398485 0.46685338906721824683 1.09600774672013729933 1.31039351315746726515 1.04853977479266395221 1.24952616061030254819 1.00944715053039424510 1...
result:
ok OK. Max delta: 0.099272
Test #7:
score: 0
Accepted
time: 0ms
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:
1.28834149803035963181 0.75059479860962955930 0.67989050997320145538 0.80508875551358215802 1.14386937711231968350 1.01559144460241094099 1.38403451919707193838 1.15451623285110588791 0.73984870806818018533 1.56857203664318184573 1.34683161345129844000 1.17583496430461227795 1.62248746896881318382 1...
result:
ok OK. Max delta: 0.098171
Test #8:
score: 0
Accepted
time: 1ms
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:
0.55856209908605820738 0.43011393485586199657 0.81339337848004970193 0.86768455725238446589 0.73680304478476510086 0.80306122152452906460 1.25514985847979465181 0.87730669312967767237 0.70577268313044480683 0.55348338628224274318 0.54589786792365596521 0.79122570299256152578 0.97521377054851963106 0...
result:
ok OK. Max delta: 0.099521
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.12214326240141983320 0.72490953800467415819 1.18817815461982192982 0.48139961320298446122 1.36024014078888501409 1.11887034132703356974 1.11726675353673169972 1.21345842559561867681 1.07225264539180324122 0.91430532272700254260 1.07984657604351825296 0.91473704504972052807 0.67301511143719357715 1...
result:
ok OK. Max delta: 0.099951
Test #10:
score: 0
Accepted
time: 4ms
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.09232053869773680730 0.28889907783756929815 0.78982009219587699726 0.88721639473742020475 -0.73729858520723372777 0.41515405045123443897 0.88527643137580933682 -0.02710484868044272618 0.70938470935158343361 1.30805645853550900923 -0.54669433732922227047 0.27837906093853050478 0.7338205652073994299...
result:
ok OK. Max delta: 0.099965
Test #11:
score: 0
Accepted
time: 1ms
memory: 3968kb
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.33305369172020082077 1.33390754960647932130 0.90107477856022272455 1.40554470493694425601 0.84913174878097446679 1.19124860773837576693 1.06040951357471627378 1.55486334862379976644 0.83769827089824876545 0.86339324625672770881 0.83061222906602287167 1.15274045130959402789 0.95364614272115199884 1...
result:
ok OK. Max delta: 0.099281
Test #12:
score: 0
Accepted
time: 3ms
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.73530118294719562521 1.57275595820508526639 1.28892659552640757902 1.77265311573620221468 1.01547981147232036143 1.45166593497825453514 1.34529082660166033529 0.73704100232385429164 1.66871843748113569798 1.15885164508878432178 1.03420772796082415901 1.46135713172186262583 1.55428597825277399523 1...
result:
ok OK. Max delta: 0.099450
Test #13:
score: 0
Accepted
time: 1ms
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.62297356182787319632 1.48463676257944428467 1.14526100054767128141 0.90928659566559132685 1.49200670976018502786 1.00564463747867311003 1.25516363809704295496 1.29938309413758750778 0.60652446721628733533 0.56927196710330300449 1.10344682005891677888 0.61109829679940322241 1.23405377378551007746 0...
result:
ok OK. Max delta: 0.099538
Test #14:
score: 0
Accepted
time: 7ms
memory: 4096kb
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:
1.03847893850741114280 0.98512974438570594939 1.33103750790378549300 1.21753753728086979422 0.85292331046308285608 1.45946468143324939730 1.53268597368091148074 1.25897462144057545417 1.15414245589457293347 0.52864160083278263519 1.28314299421506777365 0.54584807299425866847 0.96073567266475175865 0...
result:
ok OK. Max delta: 0.099750
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.44948636367616287405 1.47689891742186023694 1.22894961323969657808 1.19805111101198614933 0.99104136631881711091 0.94055653206045135328 1.46048266002799371902 1.34900615267654907874 0.82550622226693206392 0.95373628284744140643 0.71844975227196714431 1.24034221318692411797 1.15131985421229732247 1...
result:
ok OK. Max delta: 0.099491
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:
1.44326864615175721909 1.41138425815912693293 1.26206409572032219137 1.54150451963379853614 0.99275765159037573644 1.73433200481726621260 1.16543187629122446550 1.46290791359805940133 0.64829531738456995700 0.83535830128472533481 0.83486971245836949908 1.07807817561447190401 1.40645707436374519522 0...
result:
ok OK. Max delta: 0.099217
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:
1.01623296493780983338 1.44246262816806261413 1.41292375973947132990 1.34767467825915613841 0.87814870131831000927 1.56274486963428614237 1.32279596456847972727 1.52568394477920037762 0.87042779987169546329 1.27260239915691091483 0.64596801687312805756 1.12794477150239423255 1.21430535970297306773 0...
result:
ok OK. Max delta: 0.096238
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 ...