QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#283524#7521. Find the Gaplight_ink_dots#WA 1ms3916kbC++146.6kb2023-12-14 18:49:592023-12-14 18:49:59

Judging History

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

  • [2023-12-14 18:49:59]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3916kb
  • [2023-12-14 18:49:59]
  • 提交

answer

#include <algorithm>
#include <cmath>
#include <iomanip>
#include <iostream>
using namespace std;
using ld = long double;
int n;
const ld eps = 1e-9;

#define lt(x, y) ((x) < (y)-eps)
#define gt(x, y) ((x) > (y) + eps)
#define le(x, y) ((x) <= (y) + eps)
#define ge(x, y) ((x) >= (y)-eps)
#define eq(x, y) (le(x, y) && ge(x, y))
#define dot(x, y, z) (((y) - (x)) * ((z) - (x)))
#define cross(x, y, z) (((y) - (x)) ^ ((z) - (x)))
#define triple(x, y, z) ((x) * ((y) ^ (z)))

struct vec3 {
    ld x, y, z;
    vec3(ld x0 = 0, ld y0 = 0, ld z0 = 0) : x(x0), y(y0), z(z0) {}
    vec3* read() {
        scanf("%lf%lf%lf", &x, &y, &z);
        return this;
    }
    inline vec3 operator-() const { return vec3(-x, -y, -z); }
    inline vec3 operator+(const vec3& B) const { return vec3(x + B.x, y + B.y, z + B.z); }
    inline vec3 operator-(const vec3& B) const { return vec3(x - B.x, y - B.y, z - B.z); }
    inline vec3 operator*(ld k) const { return vec3(x * k, y * k); }
    inline vec3 operator/(ld k) const { return *this * (1.0 / k); }
    inline ld operator*(const vec3& B) const { return x * B.x + y * B.y + z * B.z; }
    inline vec3 operator^(const vec3& B) const {
        return vec3(y * B.z - z * B.y, z * B.x - x * B.z, x * B.y - y * B.x);
    }
    inline ld norm2() const { return x * x + y * y + z * z; }
    inline ld norm() const { return sqrt(x * x + y * y + z * z); }
    inline bool operator<(const vec3& B) const {
        return lt(x, B.x) || le(x, B.x) && (lt(y, B.y) || le(y, B.y) && lt(z, B.z));
    }
    inline bool operator==(const vec3& B) const { return eq(x, B.x) && eq(y, B.y) && eq(z, B.z); }
};

// Positive if Right-hand rule
inline ld volume(const vec3 A, const vec3 B, const vec3 C, const vec3 D) {
    return triple(B - A, C - A, D - A);
}

struct line3 {
    vec3 P, t;
    line3(vec3 _P = vec3(), vec3 _t = vec3()) : P(_P), t(_t) {}
};

inline ld dis2(const vec3 P, const line3 l) { return ((P - l.P) ^ l.t).norm2() / l.t.norm2(); }

struct plane {
    ld A, B, C, D;  // Ax + By + Cz + D = 0
    plane(ld A0 = 0.0, ld B0 = 0.0, ld C0 = 0.0, ld D0 = 0.0) : A(A0), B(B0), C(C0), D(D0) {}
    plane(const vec3& u, const vec3& v, const vec3& w) {
        vec3 t = (v - u) ^ (w - u);
        A = t.x, B = t.y, C = t.z, D = -triple(u, v, w);
    }  // > 0 if it follows Right-hand rule
    inline vec3 normVec() const { return vec3(A, B, C); }
    inline ld norm2() const { return A * A + B * B + C * C; }
    inline ld operator()(const vec3& P) const { return A * P.x + B * P.y + C * P.z + D; }
};

inline ld dis2(const vec3 P, const plane F) { return F(P) * F(P) / F.norm2(); }
bool pd(vec3 a, vec3 b, vec3 c) {
    return 0;
    ld A = fabs((a - b) * (c - b));
    ld B = fabs((a - b).norm() * (c - b).norm());
    if (fabs(A - B) < eps)
        return 1;
    return 0;
}
vec3 p[1000];
int32_t main() {
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> p[i].x >> p[i].y >> p[i].z;
    }
    ld ans = 1e18;
    for (int i = 1; i <= n; i++) {
        for (int j = i + 1; j <= n; j++) {
            for (int k = j + 1; k <= n; k++) {
                if (pd(p[i], p[j], p[k]))
                    continue;
                int gre = 0, les = 0;
                plane z(p[i], p[j], p[k]);
                ld M1 = 0, M2 = 0;
                for (int t = 1; t <= n; t++) {
                    ld pj = z(p[t]);
                    if (fabs(pj) > eps && pj < 0) {
                        M1 = max(M1, sqrt(dis2(p[t], z)));
                    }
                    if (fabs(pj) > eps && pj > 0) {
                        M2 = max(M2, sqrt(dis2(p[t], z)));
                    }
                }

                // if(les&&gre) continue;
                // ld res=0;
                // for(int t=1;t<=n;t++){
                // res=max(res,sqrt(dis2(p[t],z)));
                // }
                ans = min(ans, M1 + M2);
            }
        }
    }
    for (int i = 1; i <= n; i++) {
        for (int j = i + 1; j <= n; j++) {
            for (int k = 1; k <= n; k++) {
                if (i == k || j == k || pd(p[i], p[j], p[k]))
                    ;
                int gre = 0, les = 0;
                plane z(p[i], p[j], p[k]);
                auto v = z.normVec();
                vec3 P = p[i] + v;
                z = plane(p[i], p[j], P);
                ld M1 = 0, M2 = 0;
                for (int t = 1; t <= n; t++) {
                    ld pj = z(p[t]);
                    if (fabs(pj) > eps && pj < 0) {
                        M1 = max(M1, sqrt(dis2(p[t], z)));
                    }
                    if (fabs(pj) > eps && pj > 0) {
                        M2 = max(M2, sqrt(dis2(p[t], z)));
                    }
                }
                ans = min(ans, M1 + M2);
                z = plane(p[i], p[j], p[k] + P);
                M1 = 0, M2 = 0;
                for (int t = 1; t <= n; t++) {
                    ld pj = z(p[t]);
                    if (fabs(pj) > eps && pj < 0) {
                        M1 = max(M1, sqrt(dis2(p[t], z)));
                    }
                    if (fabs(pj) > eps && pj > 0) {
                        M2 = max(M2, sqrt(dis2(p[t], z)));
                    }
                }
                ans = min(ans, M1 + M2);
                z = plane(p[k], p[j], p[k] + P);
                M1 = 0, M2 = 0;
                for (int t = 1; t <= n; t++) {
                    ld pj = z(p[t]);
                    if (fabs(pj) > eps && pj < 0) {
                        M1 = max(M1, sqrt(dis2(p[t], z)));
                    }
                    if (fabs(pj) > eps && pj > 0) {
                        M2 = max(M2, sqrt(dis2(p[t], z)));
                    }
                }
                ans = min(ans, M1 + M2);
                z = plane(p[k], p[i], p[k] + P);
                M1 = 0, M2 = 0;
                for (int t = 1; t <= n; t++) {
                    ld pj = z(p[t]);
                    if (fabs(pj) > eps && pj < 0) {
                        M1 = max(M1, sqrt(dis2(p[t], z)));
                    }
                    if (fabs(pj) > eps && pj > 0) {
                        M2 = max(M2, sqrt(dis2(p[t], z)));
                    }
                }
                ans = min(ans, M1 + M2);

                // if(les&&gre) continue;
                // ld res=0;
                // for(int t=1;t<=n;t++){
                // res=max(res,sqrt(dis2(p[t],z)));
                // }
            }
        }
    }
    if (ans == 1e18) {
        cout << 0, exit(0);
    }
    cout << fixed << setprecision(20);
    cout << ans;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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

result:

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