QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#655309#9227. Henry the Plumberreal_sigma_teamWA 1ms4204kbC++233.2kb2024-10-19 02:45:372024-10-19 02:45:38

Judging History

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

  • [2024-10-19 02:45:38]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:4204kb
  • [2024-10-19 02:45:37]
  • 提交

answer

#include<bits/stdc++.h>

using namespace std;

constexpr int K = 3;
constexpr double PI = acos(-1);

using vec = std::array<double, K>;
using line = std::array<double, 3>;

vec operator+(const vec& a, const vec& b) {
    vec c;
    for (int i = 0; i < K; i++) {
        c[i] = a[i] + b[i];
    }
    return c;
}

vec operator-(const vec& a, const vec& b) {
    vec c;
    for (int i = 0; i < K; i++) {
        c[i] = a[i] - b[i];
    }
    return c;
}

double operator*(const vec& a, const vec& b) {
    double res = 0;
    for (int i = 0; i < K; i++) {
        res += a[i] * b[i];
    }
    return res;
}

double len(const vec& a) {
    return sqrt(a * a);
}

double angle(const vec& a, const vec& b) {
    vec c = a - b;
    return acos((a * a + b * b - c * c) / (2.0 * len(a) * len(b)));
}

line lin(const vec& norm, const vec& point) {
    line res;
    res[0] = norm[0] / len(norm);
    res[1] = norm[1] / len(norm);
    if (res[0] < 0 || (res[0] == 0 && res[1] < 0)) {
        res[0] *= -1;
        res[1] *= -1;
    }
    res[2] = -(res[0] * point[0] + res[1] * point[1]);
    return res;
}

bool operator==(const line& a, const line& b) {
    bool res = true;
    for (int i = 0; i < 3; i++) {
        res &= a[i] == b[i];
    }
    return res;
}

bool colinear(const line& a, const line& b) {
    bool res = true;
    for (int i = 0; i < 2; i++) {
        res &= a[i] == b[i];
    }
    return res;
}

vec inter(line a, line b) {
    vec res;
    res[2] = 0;
    if (b[0] == 0) {
        swap(a, b);
    }
    if (a[0] != 0) {
        double coef = a[0] / b[0];
        for (int i = 0; i < K; i++) {
            a[i] -= b[i] * coef;
        }
    }
    res[1] = -a[2] / a[1];
    res[0] = -(res[1] * b[1] + b[2]) / b[0];
    return res;
}

void solve() {
    vec norm1, point1, norm2, point2;
    cin >> point1[0] >> point1[1] >> point1[2] >> norm1[0] >> norm1[1];
    cin >> point2[0] >> point2[1] >> point2[2] >> norm2[0] >> norm2[1];
    norm1[2] = 0;
    norm2[2] = 0;
    line l1 = lin(norm1, point1);
    line l2 = lin(norm2, point2);
    if (l1 == l2) {
        cout << "2\n";
        return;
    }
    if (colinear(l1, l2)) {
        cout << "4\n";
        return;
    }
    vec point = inter(l1, l2);
    point[2] = point1[2];
    if (point == point1) {
        cout << "3\n";
        return;
    }
    point[2] = point2[2];
    if (point == point2) {
        cout << "3\n";
        return;
    }
    double l = -1000, r = 1000;
    while (r - l > 1e-5) {
        double m1 = (2 * l + r) / 3;
        double m2 = (l + 2 * r) / 3;
        point[2] = m1;
        double a1 = angle(point1 - point, point2 - point);
        point[2] = m2;
        double a2 = angle(point1 - point, point2 - point);
        if (a1 > a2) {
            r = m2;
        } else {
            l = m1;
        }
    }
    point[2] = l;
    double a = angle(point1 - point, point2 - point);
    if (a >= PI / 2) {
        cout << "3\n";
        return;
    }
    cout << "4\n";
}

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    cout << fixed << setprecision(30);
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3776kb

input:

2
-1 -1 3
1 1
2 2 3
2 2
5 5 1
3 0
7 6 -2
1 -2

output:

4
3

result:

ok 2 number(s): "4 3"

Test #2:

score: 0
Accepted
time: 1ms
memory: 4192kb

input:

100
-13 -5 -7
-19 19
-19 -13 0
-7 15
-20 20 19
-17 18
20 -20 -1
18 -19
-18 15 -14
-19 18
19 -20 6
20 -19
-12 9 1
7 -16
-13 -14 -8
8 -13
-19 16 9
20 -19
19 -18 -11
19 -18
19 20 -8
12 20
-11 -9 18
-19 -18
8 11 -13
12 -18
18 13 8
4 -18
-16 20 17
-19 18
20 -18 -3
20 -19
-17 -20 -5
-18 -19
19 16 15
19 20...

output:

4
4
4
4
4
4
3
4
4
4
3
4
4
3
3
4
3
4
4
4
4
4
4
4
4
4
4
4
3
3
3
4
4
4
4
4
4
4
4
4
4
4
4
4
3
4
4
4
4
4
3
4
3
4
4
4
3
4
4
4
4
4
4
4
3
4
3
4
4
4
4
4
4
4
4
4
4
4
4
3
4
4
4
4
4
4
4
3
3
4
3
4
4
4
4
4
4
4
4
4

result:

ok 100 numbers

Test #3:

score: 0
Accepted
time: 1ms
memory: 4148kb

input:

100
20 -9 -19
9 13
-12 14 -18
-17 12
2 -3 -2
2 -19
-8 9 -15
-19 3
-16 -16 -18
2 15
19 17 -6
-10 11
14 -20 -6
-19 7
-17 -8 -1
-7 -15
7 -15 3
2 13
-15 -9 11
15 2
-17 20 13
11 -8
-12 18 16
-18 -17
-17 15 -2
-20 1
8 -6 0
-16 -19
-5 -14 16
-17 10
-7 -16 17
-10 -13
1 1 -13
17 11
-3 -3 -18
4 -17
19 -6 -17
...

output:

3
4
4
4
3
3
4
3
3
4
4
3
4
4
3
3
4
3
4
4
4
4
3
4
3
4
4
3
3
4
4
4
3
4
3
3
4
3
3
4
3
4
3
4
3
4
3
4
4
3
3
4
3
3
4
3
3
4
4
3
3
4
4
3
4
3
3
4
3
3
3
4
3
4
3
4
3
4
3
4
4
3
3
4
3
4
4
4
4
3
3
3
3
4
3
3
4
4
4
4

result:

ok 100 numbers

Test #4:

score: 0
Accepted
time: 1ms
memory: 4204kb

input:

100
10 -9 -13
8 -7
-3 3 -15
-5 11
-14 -20 -17
13 -13
3 20 16
-20 8
-2 -15 -20
8 20
20 -10 15
12 6
4 2 20
14 14
-13 6 -20
-10 20
-18 -15 19
10 9
4 18 -11
-16 -15
20 -11 6
15 -10
-17 -19 -6
-6 8
-19 -19 -18
-11 -9
-6 4 18
11 -5
2 -18 20
0 -12
-10 -18 -17
20 -20
19 19 17
2 -11
-20 2 -16
-19 13
-6 6 -5
...

output:

4
3
4
3
4
4
3
3
3
4
4
3
3
3
4
4
3
3
3
4
4
4
3
4
3
3
3
3
4
4
3
4
4
3
4
3
3
4
4
3
3
3
4
4
3
4
4
4
4
4
3
4
3
4
4
4
3
4
4
3
4
4
3
3
3
4
3
3
3
3
4
4
4
4
3
4
4
3
4
3
4
3
3
3
4
4
3
4
3
4
4
3
4
3
4
4
3
3
4
4

result:

ok 100 numbers

Test #5:

score: -100
Wrong Answer
time: 1ms
memory: 4096kb

input:

100
4 -19 -4
4 18
-15 20 -15
-16 18
-11 -10 -13
-7 14
20 -17 0
6 -20
-12 18 -8
3 -14
20 16 17
10 17
0 19 -17
-11 6
18 -19 -7
13 -13
-17 17 -17
-5 -1
17 -13 19
-10 -12
9 -3 -19
-12 -2
-16 11 13
12 -8
17 12 11
-1 20
13 -14 -5
-4 16
-20 8 -16
16 -3
9 -3 -6
14 -12
16 4 9
-16 -10
-15 -3 -17
-20 -2
20 2 1...

output:

4
4
3
4
3
4
4
4
4
4
3
4
4
4
3
3
4
3
3
4
3
4
3
3
4
4
4
4
4
3
3
4
3
4
3
4
4
4
4
4
3
4
4
4
3
4
4
4
4
4
4
4
4
3
4
4
4
4
4
3
3
3
4
4
4
4
4
3
3
4
3
4
4
4
4
3
4
4
3
4
3
4
3
4
4
4
4
4
4
3
4
3
4
4
4
4
3
4
4
4

result:

wrong answer 13th numbers differ - expected: '3', found: '4'