QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#871422#8614. 3Ducup-team6275#TL 107ms4096kbC++233.3kb2025-01-25 20:40:512025-01-25 20:41:23

Judging History

你现在查看的是最新测评结果

  • [2025-01-25 20:41:23]
  • 评测
  • 测评结果:TL
  • 用时:107ms
  • 内存:4096kb
  • [2025-01-25 20:40:51]
  • 提交

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 >= 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: 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: 3968kb

input:

1
0.000000

output:

1.90504482321495590509 0.66869392477264066871 1.24617007957988924619

result:

ok OK. Max delta: 0.000000

Test #3:

score: 0
Accepted
time: 0ms
memory: 3968kb

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: 4096kb

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: 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:

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: 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:

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: 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:

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: 0ms
memory: 3968kb

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: 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:

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: 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.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: 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:

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: 3ms
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.63037274821503555154 1.26316379325227067399 0.56481660499102955881
0.57069249084819957272 1.40810620056423564401 0.83531468178728684028
0.79454925640570685610 1.63967808215575135632 1.31163158444338619549
1.21943367749447333526 1.39310317399778849133 0.79047582323128092764
0.73568330862329371796 0...

result:

ok OK. Max delta: 0.099503

Test #14:

score: 0
Accepted
time: 107ms
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:

1.02714901871212937535 1.01225225443874120425 0.93551934067935610818
0.80058576221759190775 1.13189828061839234212 0.93124432726315591621
0.69699701666152137245 0.73009597474179695691 1.35456306059427661369
1.84683941782394116921 0.66257076031545973676 1.35959644757125067930
1.45967923910737396032 1...

result:

ok OK. Max delta: 0.099030

Test #15:

score: 0
Accepted
time: 0ms
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:

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: 0ms
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:

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: 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.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 ...

output:


result: