QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#820510 | #4418. Laser Alarm | SGColin | AC ✓ | 155ms | 3728kb | C++20 | 2.9kb | 2024-12-18 21:39:43 | 2024-12-18 21:39:45 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define fr first
#define sc second
#define mp make_pair
#define pb push_back
#define pii pair<ll, ll>
#define rep(i, x, y) for (ll i = (x); i <= (y); ++i)
#define per(i, x, y) for (ll i = (x); i >= (y); --i)
inline ll rd() {
ll x = 0;
bool f = 0;
char c = getchar();
for (; !isdigit(c); c = getchar()) f |= (c == '-');
for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
return f ? -x : x;
}
#define N 100
typedef long long T;
struct p3 {
T x, y, z;
p3 operator + (const p3 &p) const {return {x + p.x, y + p.y, z + p.z};}
p3 operator - (const p3 &p) const {return {x - p.x, y - p.y, z - p.z};}
p3 operator * (const T &k) const {return {x * k, y * k, z * k};}
p3 operator / (const T &k) const {return {x / k, y / k, z / k};}
bool operator == (const p3 &p) const {return tie(x, y, z) == tie(p.x, p.y, p.z);}
bool operator != (const p3 &p) const {return !operator == (p);}
T operator | (const p3 &p) const {return x * p.x + y * p.y + z * p.z;}
p3 operator * (const p3 &p) const {return {y * p.z - z * p.y, z * p.x - x * p.z, x * p.y - y * p.x};}
} p[N << 1], zero{0, 0, 0};
inline T sqr (const p3 &v) {return v | v;}
inline double abs (const p3 &v) {return sqrt(sqr(v));}
inline p3 unit (const p3 &v) {return v / abs(v);}
inline T dist(const p3 &u, const p3 &v) {return abs(u - v);}
inline T prod(const p3 &a, const p3 &b, const p3 &c, const p3 &x) {
p3 w1 = x - a, w2 = b - a, w3 = c - a;
return w1 | (w2 * w3);
}
struct seg {
p3 a, b;
seg(const p3 &a = zero, const p3 &b = zero) : a(a), b(b) {}
} s[N];
inline void work() {
int n = rd();
int ans = 0;
for (int i = 1; i <= n; ++i) {
p[i].x = rd(); p[i].y = rd(); p[i].z = rd();
p[i + n].x = rd(); p[i + n].y = rd(); p[i + n].z = rd();
s[i] = (seg){p[i], p[i + n]};
}
int m = n * 2;
p[++m] = (p3){101,102,103};
p[++m] = (p3){104,105,104};
p[++m] = (p3){109,108,119};
bool fl = 0;
for (int i = 1; i <= m; ++i)
for (int j = i + 1; j <= m; ++j)
if (p[i] != p[j])
for (int k = j + 1; k <= m; ++k)
if (p[i] != p[k] && p[j] != p[k] && (p[i] - p[k]) * (p[j] - p[k]) != zero) {
fl = 1;
int cnt = 0;
for (int a = 1; a <= n; ++a) {
T w1 = prod(p[i], p[j], p[k], s[a].a);
T w2 = prod(p[i], p[j], p[k], s[a].b);
if (w1 * w2 <= 0) ++cnt;
}
//printf("%d %d %d %d\n", i, j, k, cnt);
ans = max(ans, cnt);
if (ans == n) break;
}
if (!fl) ans = n;
printf("%d\n", ans);
}
int main() {
for (int t = rd(); t; --t) work();
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 155ms
memory: 3728kb
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