QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#870875 | #8614. 3D | ucup-team4435# | TL | 92ms | 3968kb | C++20 | 2.3kb | 2025-01-25 18:02:41 | 2025-01-25 18:02:41 |
Judging History
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