QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#820510#4418. Laser AlarmSGColinAC ✓155ms3728kbC++202.9kb2024-12-18 21:39:432024-12-18 21:39:45

Judging History

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

  • [2024-12-18 21:39:45]
  • 评测
  • 测评结果:AC
  • 用时:155ms
  • 内存:3728kb
  • [2024-12-18 21:39:43]
  • 提交

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