QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#129879#6734. Click the CircleUndertrainedOverpressureWA 19ms3580kbC++237.0kb2023-07-23 02:24:012023-07-23 02:24:02

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-07-23 02:24:02]
  • 评测
  • 测评结果:WA
  • 用时:19ms
  • 内存:3580kb
  • [2023-07-23 02:24:01]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
#define TIME (clock() * 1.0 / CLOCKS_PER_SEC)

// _________ vect (2D) ______________
template <typename T>
struct vect {
    T x = 0;
    T y = 0;

    vect() = default;
    vect(T x_, T y_) : x(x_), y(y_) {}

    inline T len2() const {
        return x * x + y * y;
    }

    inline ld len() const {
        return sqrtl(len2());
    }

    inline vect rotate() const {
        return vect(-y, x);
    }
};

template <typename T>
inline istream& operator>>(istream& in, vect<T>& v) {
    return in >> v.x >> v.y;
}

template <typename T>
inline ostream& operator<<(ostream& out, const vect<T>& v) {
    return out << "[" << v.x << "," << v.y << "]";
}

template <typename T>
inline vect<T> operator+(const vect<T>& a, const vect<T>& b) {
    return vect(a.x + b.x, a.y + b.y);
}

template <typename T>
inline vect<T> operator-(const vect<T>& a, const vect<T>& b) {
    return vect(a.x - b.x, a.y - b.y);
}

template <typename T>
inline vect<T> operator*(const vect<T>& a, T k) {
    return vect(a.x * k, a.y * k);
}

template <typename T>
inline T operator*(const vect<T>& a, const vect<T>& b) {
    return a.x * b.x + a.y * b.y;
}

template <typename T>
inline T operator^(const vect<T>& a, const vect<T>& b) {
    return a.x * b.y - a.y * b.x;
}

template <typename T>
inline bool operator==(const vect<T>& a, const vect<T>& b) {
    return a.x == b.x && a.y == b.y;
}

struct tubus {
    vect<ll> a, b;
    int L, R;

    tubus(vect<ll> a, vect<ll> b, int L, int R) : a(a), b(b), L(L), R(R) {}
};

__int128 abs(__int128 x) {
    if (x < 0) {
        return -x;
    }
    return x;
}

bool check(vect<__int128> a, vect<__int128> b, vect<__int128> c, __int128 r) {
    if (b == c) {
        return (a - b).len2() <= r * r;
    }
    __int128 mn = min((a - b).len2(), (a - c).len2());
    if (((a - b) * (c - b)) <= 0 || ((a - c) * (b - c)) <= 0) {
        return mn <= r * r;
    }
    __int128 area = abs((b - a) ^ (c - a));
    return area * area <= (b - c).len2() * r * r;
}

bool on_seg(vect<__int128> a, vect<__int128> b, vect<__int128> c) {
    return ((a - c) ^ (b - c)) == 0 && ((a - c) * (b - c)) <= 0;
}

int sign(__int128 x) {
    if (x < 0) {
        return -1;
    }
    if (x == 0) {
        return 0;
    }
    return 1;
}

bool check(vect<ll> aa, vect<ll> bb, vect<ll> cc, vect<ll> dd, __int128 r) {
    vect<__int128> a(aa.x, aa.y);
    vect<__int128> b(bb.x, bb.y);
    vect<__int128> c(cc.x, cc.y);
    vect<__int128> d(dd.x, dd.y);
    if (a == b) {
        return check(a, c, d, r);
    }
    if (c == d) {
        return check(c, a, b, r);
    }
    if (on_seg(a, b, c) || on_seg(a, b, d) || on_seg(c, d, a) || on_seg(c, d, b)) {
        return true;
    }
    if (((a - c) ^ (b - c)) == 0) {
        return false;
    }
    if (((a - d) ^ (b - d)) == 0) {
        return false;
    }
    if (((c - a) ^ (d - a)) == 0) {
        return false;
    }
    if (((c - b) ^ (d - b)) == 0) {
        return false;
    }
    if (sign((c - a) ^ (d - a)) != sign((c - b) ^ (d - b)) && sign((a - c) ^ (b - c)) != sign((a - d) ^ (b - d))) {
        return true;
    }
    return check(a, c, d, r) || check(b, c, d, r) || check(c, a, b, r) || check(d, a, b, r);
}

bool check_tb_tb(tubus t1, tubus t2, int r) {
    if (t1.R < t2.L || t2.R < t1.L) {
        return false;
    }
    return check(t1.a, t1.b, t2.a, t2.b, r);
}

bool check_tb_run(tubus t1, tubus t2, ll r, int d) {
    if (check_tb_tb(t1, tubus(t2.a, t2.a, t2.L - d, t2.L), r)) {
        return true;
    }
    if (check_tb_tb(t1, tubus(t2.b, t2.b, t2.R, t2.R + d), r)) {
        return true;
    }
    int seg_l = max(t1.L, t2.L);
    int seg_r = min(t1.R, t2.R);
    if (seg_l > seg_r) {
        return false;
    }
    r *= (ll)(t2.R - t2.L);
    t1.a = t1.a * (ll)(t2.R - t2.L);
    t1.b = t1.b * (ll)(t2.R - t2.L);
    //t2.a = t2.a * (ll)(t2.R - t2.L);
    //t2.b = t2.b * (ll)(t2.R - t2.L);
    auto new_a = t2.a * (ll)(t2.R - seg_l) + t2.b * (ll)(seg_l - t2.L);
    auto new_b = t2.a * (ll)(t2.R - seg_r) + t2.b * (ll)(seg_r - t2.L);
    t2.a = new_a;
    t2.b = new_b;
    return check(t1.a, t1.b, t2.a, t2.b, r);
}

bool check_run_run(tubus t1, tubus t2, ll r, int d) {
    if (check_tb_tb(tubus(t1.a, t1.a, t1.L - d, t1.L), tubus(t2.a, t2.a, t2.L - d, t2.L), r)) {
        return true;
    }
    if (check_tb_tb(tubus(t1.a, t1.a, t1.L - d, t1.L), tubus(t2.b, t2.b, t2.R, t2.R + d), r)) {
        return true;
    }
    if (check_tb_tb(tubus(t1.b, t1.b, t1.R, t1.R + d), tubus(t2.a, t2.a, t2.L - d, t2.L), r)) {
        return true;
    }
    if (check_tb_tb(tubus(t1.b, t1.b, t1.R, t1.R + d), tubus(t2.b, t2.b, t2.R, t2.R + d), r)) {
        return true;
    }
    int seg_l = max(t1.L, t2.L);
    int seg_r = min(t1.R, t2.R);
    if (seg_l > seg_r) {
        return false;
    }
    r *= (ll)(t2.R - t2.L) * (ll)(t1.R - t1.L);
    t1.a = t1.a * (ll)(t2.R - t2.L);
    t1.b = t1.b * (ll)(t2.R - t2.L);
    t2.a = t2.a * (ll)(t1.R - t1.L);
    t2.b = t2.b * (ll)(t1.R - t1.L);
    {
        auto new_a = t2.a * (ll)(t2.R - seg_l) + t2.b * (ll)(seg_l - t2.L);
        auto new_b = t2.a * (ll)(t2.R - seg_r) + t2.b * (ll)(seg_r - t2.L);
        t2.a = new_a;
        t2.b = new_b;
    }
    {
        auto new_a = t1.a * (ll)(t1.R - seg_l) + t1.b * (ll)(seg_l - t1.L);
        auto new_b = t1.a * (ll)(t1.R - seg_r) + t1.b * (ll)(seg_r - t1.L);
        t1.a = new_a;
        t1.b = new_b;
    }
    return check(vect<ll>(), vect<ll>(), t2.a - t1.a, t2.b - t1.b, r);
}

void solve() {
    int n, r, d;
    cin >> n >> r >> d;
    r *= 2;
    vector<tubus> tb, run;
    for (int i = 0; i < n; i++) {
        int type;
        cin >> type;
        if (type == 1) {
            vect<ll> c;
            int t;
            cin >> c >> t;
            tb.emplace_back(c, c, t - d, t + d);
        } else {
            vect<ll> c, s;
            int u, v;
            cin >> c >> s >> u >> v;
            tb.emplace_back(c, s, u - d, v + d);
            run.emplace_back(c, s, u, v);
        }
    }
    int ans = 0;
    for (int i = 0; i < tb.size(); i++) {
        for (int j = i + 1; j < tb.size(); j++) {
            if (check_tb_tb(tb[i], tb[j], r)) {
                ans++;
            }
        }
    }
    for (int i = 0; i < tb.size(); i++) {
        for (int j = 0; j < run.size(); j++) {
            if (check_tb_run(tb[i], run[j], r, d)) {
                ans++;
            }
        }
    }
    for (int i = 0; i < run.size(); i++) {
        for (int j = i + 1; j < run.size(); j++) {
            if (check_run_run(run[i], run[j], r, d)) {
                ans++;
            }
        }
    }
    cout << ans << "\n";
}

int main() {
#ifdef ONPC
    freopen("input", "r", stdin);
#endif
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    int t = 1;
    //cin >> t;
    while (t--) {
        solve();
    }

    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3464kb

input:

2 1 1
1 1 1 2
1 2 2 3

output:

1

result:

ok 1 number(s): "1"

Test #2:

score: 0
Accepted
time: 1ms
memory: 3528kb

input:

2 1 1
1 1 1 2
1 3 2 3

output:

0

result:

ok 1 number(s): "0"

Test #3:

score: 0
Accepted
time: 1ms
memory: 3464kb

input:

2 1 1
1 3 3 2
2 5 5 5 1 2 4

output:

3

result:

ok 1 number(s): "3"

Test #4:

score: 0
Accepted
time: 1ms
memory: 3508kb

input:

2 1 1
2 1 1 1 5 2 4
2 5 5 5 1 2 4

output:

2

result:

ok 1 number(s): "2"

Test #5:

score: 0
Accepted
time: 1ms
memory: 3528kb

input:

2 1 1
2 10 1 10 20 2 4
2 1 10 20 10 2 4

output:

6

result:

ok 1 number(s): "6"

Test #6:

score: -100
Wrong Answer
time: 19ms
memory: 3580kb

input:

1000 8 4
1 8323 2820 943
1 8246 2850 944
1 8177 2880 941
1 8154 2866 944
2 8325 8146 2865 2846 943 944
1 8349 2891 939
2 8176 8344 2888 2692 940 945
1 8191 2732 945
1 8144 2668 945
2 8182 8191 2889 2844 939 940
1 8173 2687 941
1 8241 2870 945
2 8266 8344 2910 2667 942 943
1 8169 2863 939
1 8349 2921...

output:

22528

result:

wrong answer 1st numbers differ - expected: '22721', found: '22528'