QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#197763#7521. Find the GapayerszWA 1ms3600kbC++203.6kb2023-10-02 19:36:482023-10-02 19:36:49

Judging History

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

  • [2023-10-02 19:36:49]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3600kb
  • [2023-10-02 19:36:48]
  • 提交

answer

/*
 *@author:Ayersz127
 *@time: 2023-10-02
 */
#include <bits/stdc++.h>

// #define MULTITEST

using i64 = long long;
using u64 = unsigned long long;
using i128 = __int128_t;
using ld = long double;

template <typename T>
bool cmax(T &x, const T &y) {
    return x < y ? x = y, 1 : 0;
}
 
template <typename T>
bool cmin(T &x, const T &y) {
    return x > y ? x = y, 1 : 0;
}

const int N = 55;

struct point {
    ld x, y, z;
    point(ld x = 0, ld y = 0, ld z = 0) : x(x), y(y), z(z) {}
    point operator-(const point &rhs) const {
        return point(x - rhs.x, y - rhs.y, z - rhs.z);
    }
    ld len() const {
        return sqrt(x * x + y * y + z * z);
    }
} p[N];

using vec = point;

const ld EPS = 1e-10;

int sgn(ld x) {
    if (std::abs(x) < EPS) {
        return 0;
    } else {
        return x < 0 ? -1 : 1;
    }
}

vec crs(vec a, vec b) {
    return vec(a.y * b.z - a.z * b.y, a.z * b.x - a.x * b.z, a.x * b.y - b.x * a.y);
}

int n;

void solve(int tc) {
    std::cin >> n;

    for (int i = 0; i < n; i++) {
        std::cin >> p[i].x >> p[i].y >> p[i].z;
    }

    // 三点搞一个面
    ld ans = 1e18;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            for (int k = 0; k < n; k++) {
                vec v0 = p[j] - p[i], v1 = p[k] - p[i];
                vec h = crs(v0, v1);

                ld A = h.x, B = h.y, C = h.z, D0, dis = 0;
                D0 = -A * p[i].x - B * p[i].y - C * p[i].z;
                
                int f = 0;
                bool flag = 1;
                for (int t = 0; t < n; t++) {
                    double D1 = -A * p[t].x - B * p[t].y - C * p[t].z;
                    if (sgn(D0 - D1) == 0) {
                        continue;
                    }
                    if (f == 0) {
                        f = (D0 > D1) ? 1 : -1;
                    }
                    if ((D0 > D1 && f == -1) || (D0 < D1 && f == 1)) {
                        flag = 0;
                        break;
                    }
                    dis = std::max(dis, std::abs(D0 - D1) / h.len());
                }

                if (flag) {
                    ans = std::min(ans, dis);
                }
            }
        }
    }

    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            for (int k = 0; k < n; k++) {
                for (int t = k + 1; t < n; t++) {
                    vec v0 = p[j] - p[i], v1 = p[t] - p[k];
                    vec h = crs(v0, v1);

                    ld A = h.x, B = h.y, C = h.z, D0, D1;
                    D0 = -A * p[i].x - B * p[i].y - C * p[i].z;
                    D1 = -A * p[k].x - B * p[k].y - C * p[k].z;
                    bool flag = true;

                    for (int u = 0; u < n; u++) {
                        ld Dx = -A * p[u].x - B * p[u].y - C * p[u].z;
                        if (sgn(Dx - D0) * sgn(Dx - D1) > 0) {
                            flag = false;
                            break;
                        }
                    }

                    if (flag) {
                        ans = std::min(ans, std::abs(D0 - D1) / h.len());
                    }
                }
            }
        }
    }

    std::cout << ans << "\n";
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    std::cout << std::fixed << std::setprecision(15);
    int t = 1;
#ifdef MULTITEST
    std::cin >> t;
#endif
    for (int i = 1; i <= t; i++) {
        solve(i);
    }
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 1ms
memory: 3600kb

input:

8
1 1 1
1 1 2
1 2 1
1 2 2
2 1 1
2 1 2
2 2 1
2 2 2

output:

0.000000000000000

result:

wrong answer 1st numbers differ - expected: '1.0000000', found: '0.0000000', error = '1.0000000'