QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#49762 | #4418. Laser Alarm | lqhsmash | AC ✓ | 430ms | 3736kb | C++20 | 2.1kb | 2022-09-22 21:53:40 | 2022-09-22 21:53:43 |
Judging History
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