QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#283506#7521. Find the Gaplight_ink_dots#WA 25ms4008kbC++144.2kb2023-12-14 18:24:422023-12-14 18:24:43

Judging History

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

  • [2023-12-14 18:24:43]
  • 评测
  • 测评结果:WA
  • 用时:25ms
  • 内存:4008kb
  • [2023-12-14 18:24:42]
  • 提交

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) {
    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 = 1; k <= n; k++) {
                if (i == k || j == k || pd(p[i], p[j], p[k]))
                    continue;
                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)));
                    }
                }

                // 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);
            }
        }
    }
    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: 100
Accepted
time: 1ms
memory: 4008kb

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:

1.00000000000000000000

result:

ok found '1.000000000', expected '1.000000000', error '0.000000000'

Test #2:

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

input:

5
1 1 1
1 2 1
1 1 2
1 2 2
2 1 1

output:

0.70710678118654752438

result:

ok found '0.707106781', expected '0.707106781', error '0.000000000'

Test #3:

score: 0
Accepted
time: 2ms
memory: 3860kb

input:

50
973 1799 4431
1036 1888 4509
1099 1977 4587
1162 2066 4665
1225 2155 4743
1288 2244 4821
1351 2333 4899
1414 2422 4977
1540 2600 5133
1603 2689 5211
1666 2778 5289
1729 2867 5367
1792 2956 5445
1855 3045 5523
1918 3134 5601
1981 3223 5679
2044 3312 5757
2107 3401 5835
2170 3490 5913
2296 3668 606...

output:

0

result:

ok found '0.000000000', expected '0.000000000', error '-0.000000000'

Test #4:

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

input:

50
4532 3245 1339
4624 3260 1345
4716 3275 1351
4808 3290 1357
4900 3305 1363
5084 3335 1375
5176 3350 1381
5268 3365 1387
5360 3380 1393
5452 3395 1399
5544 3410 1405
5728 3440 1417
5820 3455 1423
5912 3470 1429
6096 3500 1441
6188 3515 1447
6280 3530 1453
6372 3545 1459
6464 3560 1465
6556 3575 14...

output:

0

result:

ok found '0.000000000', expected '0.000000000', error '-0.000000000'

Test #5:

score: -100
Wrong Answer
time: 25ms
memory: 3968kb

input:

50
1 70 7443
1 138 5063
2 109 5971
3 23 8874
3 152 4359
4 59 7507
5 50 7715
5 73 6910
7 25 8376
7 103 5646
8 3 9039
9 83 6132
9 142 4067
10 124 4590
11 140 3923
12 168 2836
13 46 6999
13 84 5669
13 189 1994
13 229 594
15 171 2410
16 94 4998
20 38 6530
20 125 3485
21 78 5023
22 210 296
23 117 3444
25...

output:

211.23938549322081935367

result:

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