QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#871519#8614. 3Ducup-team6275#TL 8ms4096kbC++234.2kb2025-01-25 20:58:262025-01-25 20:58:26

Judging History

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

  • [2025-01-25 20:58:26]
  • 评测
  • 测评结果:TL
  • 用时:8ms
  • 内存:4096kb
  • [2025-01-25 20:58:26]
  • 提交

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() * 5;
            pts[i].y = get_random_ld() * 5;
            pts[i].z = get_random_ld() * 5;
        }

        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;
}

Details

Tip: Click on the bar to expand more detailed information

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.26619833415110989369 -0.25642656086814166055 -0.03551848389833465016
-0.12292968759550952705 0.27771023708019094793 0.02158741085921891218
-0.23729670596100573715 -0.05828697397302510055 0.24271933288001083079
0.09402805940540537115 0.03700329776097581349 -0.22878825984089509260

result:

ok OK. Max delta: 0.098429

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

input:

2
0.000000 0.938096
0.938096 0.000000

output:

0.03725671336321126868 0.39699447163237374173 -0.24700881179970870724
-0.03725671336321126868 -0.39699447163237374129 0.24700881179970870724

result:

ok OK. Max delta: 0.000000

Test #4:

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

input:

3
0.000000 0.769195 0.308169
0.769195 0.000000 0.686850
0.308169 0.686850 0.000000

output:

0.26519105541981111916 -0.12219047540538932866 -0.09856349919445984021
-0.31640904837435109134 -0.01718395527384011367 0.32611934079471720173
0.05121799295453997218 0.13937443067922944189 -0.22755584160025736184

result:

ok OK. Max delta: 0.053549

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.32829099641527458877 0.09544507851212833630 -0.06277529167492913286
0.03556451456105817115 -0.12661498024503344147 -0.26550905607925893081
-0.12054810088920902016 -0.17206493013744902617 0.00418406898445107458
-0.28869126375981648798 0.34720799068187631776 0.09493891079187300451
0.701965846503241...

result:

ok OK. Max delta: 0.098565

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.20526084133553302875 0.34013552745163845082 -0.40645588599945363167
0.30424421456820311175 -0.50443326120317997867 -0.23930226172020208639
0.17367187249719735591 -0.19539763870628788257 0.01659548729146981846
-0.41762357288400186561 0.01557257202096831695 0.44480171623420226000
-0.096975876220974...

result:

ok OK. Max delta: 0.099527

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:

0.24919580862904895343 0.01580322388771014056 0.33336749186229084761
-0.31463096942241171598 -0.34969400789961376094 0.23495510887529501504
0.10025095370845109658 0.08767090195574409853 -0.01795407714921829628
-0.32455888688723925385 0.35195170103857258614 -0.18259508934755230326
0.45010487025117326...

result:

ok OK. Max delta: 0.099747

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:

0.03733593354046749386 -0.02397270109902487935 0.37266437942337261890
-0.00928993885911405786 -0.07530457846343380766 -0.12809030878913834619
-0.22938862143863093064 0.00819667205003693337 -0.48763159085100127028
0.08860937770685369647 0.00124260002238736253 0.26246241859532980657
-0.457102349078244...

result:

ok OK. Max delta: 0.099672

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.22765966733632366859 0.37868843664062286206 0.08933800947431678129
-0.49599374023084135570 0.06316840606392263864 -0.24728113103851248589
0.16592699579080021511 -0.11862931977201465793 -0.02915360034629481639
0.05678675172764665875 0.07525166312316149586 -0.24206308025474479505
-0.4064804264829035...

result:

ok OK. Max delta: 0.099548

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:

-0.64555703391499528359 0.15387189578963030284 0.08887828172826676000
0.43815380480328831089 -0.15956195664606917560 -0.02656316470505227720
-0.26232692240310510575 0.14433237977395765210 0.13191663605975172515
0.09945143171952801038 -0.44782180185348316871 -0.26989031419058549409
0.1539954200091884...

result:

ok OK. Max delta: 0.098178

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:

-0.26306917783882151720 0.02011566313220039797 0.00629321633688576529
0.08388218480735105140 -0.28824988332596820765 -0.30866289431128462279
-0.25447375766697818674 0.23494651016847801529 0.27345368591576836494
0.36243098895654996634 -0.27554308555209665191 0.11008102605307075223
0.46838581214548781...

result:

ok OK. Max delta: 0.099613

Test #12:

score: 0
Accepted
time: 1ms
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.12017821613840450263 0.10873575457831025299 0.34087878156013095426
-0.35364283429686805128 0.21972377922893675272 -0.03110910799506951094
-0.56899895159538327414 -0.14372363919063125084 -0.33148923977809601491
-0.12787873531856635135 -0.32417247823122737321 -0.28746800810316463495
0.40724770594357...

result:

ok OK. Max delta: 0.098891

Test #13:

score: 0
Accepted
time: 0ms
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.44808034944074222523 0.15563547816471740861 0.39239460603680358596
0.36677138931276028486 -0.15199933809181675299 0.22471746090429729108
0.06122232153225263401 -0.31408402193462150564 -0.26117968012752588026
0.37872946795850518254 0.26077390480748687527 -0.25229758912988701743
-0.50462600482206384...

result:

ok OK. Max delta: 0.097772

Test #14:

score: 0
Accepted
time: 8ms
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.30985897391633351059 0.03446725561722994578 -0.07960121611268440589
0.42022346015407379826 -0.01226839217116333452 -0.30535190194082917651
0.25227361449322965761 -0.61477855190726562367 -0.04365927406943194942
-0.18520106805160098775 0.06202043930348008429 0.71670864811961203515
-0.466329128646229...

result:

ok OK. Max delta: 0.099571

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:

-0.50166463158550412085 0.21864177017167164894 0.00180925348030023234
-0.00916297702075604271 -0.10137584473763414030 -0.27746829394864944954
-0.46088199477452164638 -0.00846407259354936417 -0.28458881509963179042
0.42449627137784064885 0.05346389904978756432 -0.19852006111555172210
-0.1816051127824...

result:

ok OK. Max delta: 0.099252

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:

-0.30968611685474327453 -0.01434637947347451332 -0.05321289839077713831
0.08690683536148049537 -0.02665032352606665385 -0.55620563770229603439
-0.38130754372820987845 0.24998962475533493622 0.53390548111593988910
0.35595805426455654570 -0.18529021973551251215 0.39890782876817910767
0.216267824519852...

result:

ok OK. Max delta: 0.099233

Test #17:

score: 0
Accepted
time: 0ms
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.36914888308660435046 -0.11517476642953727493 0.27261080607453037320
-0.23890237744908730051 0.02142410523967497120 -0.38300136479602387546
-0.02890618118785518733 0.42364489902588832243 0.38879174120579173819
0.23297380911092649153 -0.04483062046627249507 -0.35622410459864510611
0.206490101176961...

result:

ok OK. Max delta: 0.099495

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: