QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#48752#4390. KeychainslqhsmashWA 4ms3740kbC++203.6kb2022-09-15 16:43:242022-09-15 16:43:25

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-09-15 16:43:25]
  • 评测
  • 测评结果:WA
  • 用时:4ms
  • 内存:3740kb
  • [2022-09-15 16:43:24]
  • 提交

answer

#include <bits/stdc++.h>
#define ll long long
#define endl '\n'

using namespace std;

const int inf = 0x3f3f3f3f;
const int N = 2e5 + 50;
const double eps = 1e-8;

int sgn (double x) {
    if (fabs (x) < eps) return 0;
    return x < 0 ? -1 : 1;
}

struct Point {
    double x, y, z;
    Point () { x = y = z = 0; }
    Point (double x, double y, double z): x(x), y(y), z(z) {}
    Point operator + (Point r) { return Point(x + r.x, y + r.y, z + r.z); }
    Point operator - (Point r) { return Point(x - r.x, y - r.y, z - r.z); }
    Point operator * (double r) { return Point(r * x, r * y, r * z); }
    Point operator / (double r) { return Point(x / r, y / r, z / r); }
    bool operator == (Point r) { 
        return sgn (r.x - x) == 0 && sgn (r.y - y) == 0 && sgn (r.z - z) == 0;
    }
    void show () {
        cerr << "x = " << x << ", y = " << y << ", z = " << z << endl;
    }
};

Point Cross (Point a, Point b) {
    return Point (a.y*b.z-b.y*a.z, -(a.x*b.z-a.z*b.x), a.x*b.y-a.y*b.x);
}

double Dot (Point a, Point b) {
    return a.x * b.x + a.y * b.y + a.z * b.z;
}

double Dist (Point a, Point b) {
    double res = (a.x - b.x) * (a.x - b.x);
    res += (a.y - b.y) * (a.y - b.y);
    res += (a.z - b.z) * (a.z - b.z);
    return sqrt (res);
}

double Dot2 (double a, double b, double c, double d) {
    return a * c - b * d;
}

Point solve (Point a, Point b, double c1, double c2) {
    if (sgn (a.y) == 0 && sgn (b.y) == 0) {
        double z = (b.z * c1 - a.z * c2) / (b.z * a.x - a.z * b.x);
        double x = (b.x * c1 - a.x * c2) / (b.x * a.z - b.z * a.x);
        return Point (x, 0, z);
    }
    if (sgn (a.z) == 0 && sgn (b.z) == 0) {
        double x = (b.x * c1 - a.x * c2) / (b.x * a.y - a.x * b.y);
        double y = (b.y * c1 - a.y * c2) / (b.y * a.x - b.x * a.y);
        return Point (x, y, 0);
    }
    double y = (b.z * c1 - a.z * c2) / (b.z * a.y - a.z * b.y);
    double z = (b.y * c1 - a.y * c2) / (b.y * a.z - b.z * a.y);
    return Point (0, y, z);
}

int T;
Point p1, v1, p2, v2;
double r1, r2;

void work (Point p, Point v) {
    double a = Dot (v, v);
    double b = 2 * Dot (p - p1, p);
    double c = Dot (p - p1, p - p1) - r1 * r1;
    double delta = b * b - 4 * a * c;
    // cerr << a << ' ' << b << ' ' << c << ' ' << delta << "  hh" << endl;
    if (sgn (delta) < 0) {
        printf("NO\n");
    }else {
        delta = sqrt (delta);
        // cerr << delta << endl;
        double t1 = (-b + delta) / (2 * a);
        double t2 = (-b - delta) / (2 * a);
        // cerr << t1 << ' ' << t2 << endl;
        Point ok1 = p + v * t1, ok2 = p + v * t2;
        // ok1.show (), ok2.show ();
        if (Dist (ok1, p2) < r2 && Dist (ok2, p2) > r2) {
            printf("YES\n");
            return ;
        }
        if (Dist (ok2, p2) < r2 && Dist (ok1, p2) > r2) {
            printf("YES\n");
            return ;
        }
        printf("NO\n");
    }
}

int main() {
#ifdef LOCAL
    clock_t c1 = clock();
    freopen("in.in", "r", stdin);
    freopen("out.out", "w", stdout);
#endif
    // =================================================    
    scanf ("%d", &T);
    while (T --) {
        scanf ("%lf%lf%lf%lf%lf%lf%lf", &p1.x, &p1.y, &p1.z, &v1.x, &v1.y, &v1.z, &r1);
        scanf ("%lf%lf%lf%lf%lf%lf%lf", &p2.x, &p2.y, &p2.z, &v2.x, &v2.y, &v2.z, &r2);
        Point v = Cross (v1, v2), p = solve (v1, v2, Dot (p1, v1), Dot (p2, v2));;
        work (p, v);
    }
    // =================================================    
#ifdef LOCAL
    cerr << "Time Used = " << clock() - c1 << "ms" << endl;
#endif
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 4ms
memory: 3740kb

input:

1000
30 -39 -96 941 -777 -411 410
618 -648 -252 -360 -408 -154 259
106 -454 754 -435 446 -146 53
856 -987 -123 -164 367 -117 384
-41 -366 -776 -658 473 93 81
-615 -987 107 616 999 762 512
-865 -570 737 245 -313 -916 323
-307 -496 -348 31 332 803 610
-475 907 181 763 979 -919 77
858 119 420 -884 -369...

output:

NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
YES
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO...

result:

wrong answer 1st lines differ - expected: 'No', found: 'NO'