QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#49762#4418. Laser AlarmlqhsmashAC ✓430ms3736kbC++202.1kb2022-09-22 21:53:402022-09-22 21:53:43

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-22 21:53:43]
  • 评测
  • 测评结果:AC
  • 用时:430ms
  • 内存:3736kb
  • [2022-09-22 21:53:40]
  • 提交

answer

#include <bits/stdc++.h>
#define ll long long
using namespace std;

const int MOD = 998244353;
const int N = 55;

struct Point {
    int x, y, z;
    Point (int x=0, int y=0, int z=0): 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 * (int r) { return Point (x*r, y*r, z*r); }
    bool operator == (Point r) { return x==r.x&&y==r.y&&z==r.z; }
    bool operator != (Point r) { return x!=r.x||y!=r.y||z!=r.z; }
    void input () { scanf ("%d%d%d", &x, &y, &z); }
    void show () { printf("x = %d, y = %d, z = %d\n", x, y, z); }
};

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

struct Line {
    Point p, v;
};

Line get_plane (Point a, Point b, Point c) {
    return { a,  Cross (a - b, a - c) };
}

int T, n, m;
Point p[N << 1];
Line li[N];

int check (Line plane) {
    int res = 0;
    for (int i = 1; i <= n; i ++){
        int d1 = Dot (li[i].p - plane.p, plane.v);
        int d2 = Dot (li[i].v - plane.p, plane.v);
        res += (d1 >= 0 && d2 <= 0) || (d1 <= 0 && d2 >= 0);
    }
    return res;
}

int main () {
    scanf ("%d", &T);
    while (T -- ){
        scanf ("%d", &n);
        m = 0;
        for (int i = 1; i <= n; i ++) {
            li[i].p.input ();
            li[i].v.input ();
            p[++ m] = li[i].p;
            p[++ m] = li[i].v;
        }

        int ans = 0, flag = 1;
        for (int i = 1; i <= m; i ++) {
            for (int j = i + 1; j <= m; j ++) {
                for (int k = j + 1; k <= m; k ++) {
                    if (Cross (p[i] - p[j], p[i] - p[k]) == Point()) continue;
                    flag = 0;
                    Line plane = get_plane (p[i], p[j], p[k]);
                    ans = max (ans, check (plane));
                }
            }
        }
        if (flag) ans = n;

        printf("%d\n", ans);
    }

    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 430ms
memory: 3736kb

input:

10
50
94 57 39 12 69 59
86 46 44 17 32 83
35 86 71 47 41 50
68 93 71 54 28 25
92 74 2 30 60 86
87 52 54 32 17 88
51 63 96 23 12 69
1 82 85 20 9 90
25 72 42 49 4 52
30 86 94 93 43 34
10 45 30 85 32 75
84 37 71 37 78 19
28 30 7 40 10 77
5 68 86 83 3 41
71 73 8 86 69 48
65 11 6 49 64 50
61 2 24 60 11 9...

output:

33
39
36
36
40
37
34
33
50
50

result:

ok 10 lines