QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#49691#4418. Laser AlarmlqhsmashRE 0ms0kbC++202.4kb2022-09-22 13:25:542022-09-22 13:25:57

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 13:25:57]
  • 评测
  • 测评结果:RE
  • 用时:0ms
  • 内存:0kb
  • [2022-09-22 13:25:54]
  • 提交

answer

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

const int N = 5e3 + 50;

int T, n;

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); }
    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); }
};

struct Line {
    Point p, v;
};

Point Cross (Point a, Point b) {
    return Point (a.y*b.z - a.z*b.y, -(a.x*b.z - a.z*b.x), 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;
}

Line build (Line a, Line b) {
    Point v1 = Cross (a.v, b.v);
    Point v2 = Cross (a.p - b.p, b.v);
    if (v1 != Point ()) return {a.p, v1};
    return {a.p, v2};
}

Line p[N];

bool allsame () {
    for (int i = 2; i <= n; i ++) {
        Point v1 = Cross (p[1].v, p[i].v);
        Point v2 = Cross (p[1].p - p[i].p, p[i].v);
        if (v1 != Point () || v2 != Point ()) return false;
    }
    return true;
}

bool check (Line plane, Line a) {
    if (Dot (plane.p - (a.p + a.v), plane.v)) return false;
    if (Dot (plane.p - (a.p - a.v), plane.v)) return false;
    return true;
}

int solve (Line plane) {
    int ans = 0;
    for (int i = 1; i <= n; i ++) {
        ans += check (plane, p[i]);
    }
    return ans;
}


int main () {
    freopen ("in.in", "r", stdin);
    freopen ("out.out", "w", stdout);

    scanf ("%d", &T);
    while (T --) {
        scanf ("%d", &n);
        for (int i = 1; i <= n; i ++) {
            Point p1, p2;
            p1.input (), p2.input ();
            p[i] = {p1, p1 - p2};
        }
        if (allsame ()) {
            printf("%d\n", n);
            continue;
        }
        int ans = 1;
        for (int i = 1; i <= n; i ++) {
            for (int j = i + 1; j <= n; j ++) {
                Line plane = build (p[i], p[j]);
                if (plane.v == Point ()) continue;
                ans = max (solve (plane), ans);
            }
        }
        printf("%d\n", ans);
    }

    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Dangerous Syscalls

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:


result: