QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#870875#8614. 3Ducup-team4435#TL 92ms3968kbC++202.3kb2025-01-25 18:02:412025-01-25 18:02:41

Judging History

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

  • [2025-01-25 18:02:41]
  • 评测
  • 测评结果:TL
  • 用时:92ms
  • 内存:3968kb
  • [2025-01-25 18:02:41]
  • 提交

answer

#pragma GCC optimize("unroll-loops,O3")

#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using ld = double;

#define all(a) begin(a), end(a)
#define len(a) int((a).size())

using P = array<int, 3>;

const int N = 100;

int sqr(int x) {
    return x * x;
}

int dist(P a, P b) {
    return sqr(a[0] - b[0]) + sqr(a[1] - b[1]) + sqr(a[2] - b[2]);
}

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    cout << fixed << setprecision(10);

    int n;
    cin >> n;
    vector<vector<ld>> dists(n, vector<ld>(n));
    for (auto &v : dists) {
        for (auto &x : v) {
            cin >> x;
            x = x * x * N * N;
        }
    }

    while (true) {

        vector<P> ans(n);
        ans[0] = {0, 0, 0};
        for (int i = 1; i < n; i++) {
            ld best = 1e18;
            for (int x = -N; x <= N; x++) {
                for (int y = -N; y <= N; y++) {
                    for (int z = -N; z <= N; z++) {
                        ld sum = 0;
                        for (int j = 0; j < i; j++) {
                            sum = max(sum, fabs(dists[i][j] - dist(ans[j], {x, y, z})));
                            // sum += dists[i][j] - dist(ans[j], {x, y, z});
                        }
                        if (sum < best) {
                            best = sum;
                            ans[i] = {x, y, z};
                        }
                    }
                }
            }
        }

        auto get_error = [&]() {
            ld max_error = 0;
            for (int i = 0; i < n; i++) {
                for (int j = i + 1; j < n; j++) {
                    ld cur_dist = dist(ans[i], ans[j]);
                    cur_dist /= N * N;
                    ld expected = dists[i][j] / N / N;
                    cur_dist = sqrt(cur_dist);
                    expected = sqrt(expected);
                    max_error = max(max_error, fabs(expected - cur_dist));
                }
            }
            return max_error;
        };

        if (get_error() > 0.0999) {
            continue;
        }
        // cerr << "error: " << get_error() << '\n';
        for (auto [x, y, z] : ans) {
            cout << ld(x) / N << ' ' << ld(y) / N << ' ' << ld(z) / N << '\n';
        }
        return 0;
    }
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

0.0000000000 0.0000000000 0.0000000000
-0.6600000000 -0.3600000000 -0.1000000000
-0.2400000000 -0.4700000000 0.1800000000
-0.3500000000 -0.0400000000 -0.1500000000

result:

ok OK. Max delta: 0.003858

Test #2:

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

input:

1
0.000000

output:

0.0000000000 0.0000000000 0.0000000000

result:

ok OK. Max delta: 0.000000

Test #3:

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

input:

2
0.000000 0.938096
0.938096 0.000000

output:

0.0000000000 0.0000000000 0.0000000000
-0.8400000000 -0.4000000000 -0.1200000000

result:

ok OK. Max delta: 0.000013

Test #4:

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

input:

3
0.000000 0.769195 0.308169
0.769195 0.000000 0.686850
0.308169 0.686850 0.000000

output:

0.0000000000 0.0000000000 0.0000000000
-0.7500000000 -0.1600000000 -0.0600000000
-0.0800000000 -0.2200000000 -0.2000000000

result:

ok OK. Max delta: 0.000273

Test #5:

score: -100
Time Limit Exceeded

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:


result: