QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#338399#5570. Epidemic Escapeucup-team1198WA 166ms5856kbC++208.6kb2024-02-25 21:18:452024-02-25 21:18:45

Judging History

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

  • [2024-02-25 21:18:45]
  • 评测
  • 测评结果:WA
  • 用时:166ms
  • 内存:5856kb
  • [2024-02-25 21:18:45]
  • 提交

answer

#pragma GCC optimize("fast-math,Ofast,unroll-loops")
#include <map>
#include <set>
#include <array>
#include <cmath>
#include <deque>
#include <bitset>
#include <random>
#include <string>
#include <vector>
#include <cassert>
#include <complex>
#include <iomanip>
#include <iostream>
#include <algorithm>
#include <unordered_map>
#include <unordered_set>

using namespace std;

#define int int64_t
using ld = __float128;

ld abs(ld x) {
    if (x > 0) return x;
    return -x;
}

struct IVector {
    int x;
    int y;

    IVector(int x = 0, int y = 0): x(x), y(y) {}
    IVector(const IVector& a, const IVector& b): x(b.x - a.x), y(b.y - a.y) {}
};

IVector operator-(const IVector& a) {
    return {-a.x, -a.y};
}

int operator%(const IVector& a, const IVector& b) {
    return a.x * b.y - a.y * b.x;
}

bool hp(const IVector& v) {
    if (v.y == 0) return v.x > 0;
    return v.y > 0;
}

bool operator<(const IVector& a, const IVector& b) {
    if (hp(a) != hp(b)) return hp(a);
    return a % b > 0;
}

bool operator==(const IVector& a, const IVector& b) {
    return a.x == b.x && a.y == b.y;
}

istream& operator>>(istream& in, IVector& v) {
    in >> v.x >> v.y;
    return in;
}

const int MAXN = 1e5 + 100;
bool is_bad[MAXN];

struct Vector {
    ld x;
    ld y;

    Vector(ld x = 0, ld y = 0): x(x), y(y) {}
    Vector(const Vector& a, const Vector& b): x(b.x - a.x), y(b.y - a.y) {}
    Vector(const IVector& a): x(a.x), y(a.y) {}
    Vector(const IVector& a, bool inv) {
        ld ln = a.x * a.x + a.y * a.y;
        x = a.x; y = a.y;
        x /= ln;
        y /= ln;
    }

    ld sqlen() const { return x * x + y * y; }
};

Vector operator-(const Vector& a, const Vector& b) {
    return Vector(b, a);
}

Vector operator+(const Vector& a, const Vector& b) {
    return {a.x + b.x, a.y + b.y};
}

ld operator%(const Vector& a, const Vector& b) {
    return a.x * b.y - a.y * b.x;
}

ld operator*(const Vector& a, const Vector& b) {
    return a.x * b.x + a.y * b.y;
}

const ld EPS = 1e-32;

const int MAXK = 5;

vector<Vector> convex(vector<Vector>& p) {
    if (p.empty()) return p;
    if ((int)p.size() == 1) {
        vector<Vector> p1 = p;
        p.clear();
        return p1;
    }
    int n = p.size();
    Vector minp = p[0];
    for (int i = 1; i < n; ++i) {
        if (p[i].x < minp.x) {
            minp = p[i];
        } else if (p[i].x == minp.x && p[i].y < minp.y) {
            minp = p[i];
        }
    }
    sort(p.begin(), p.end(), [&](const Vector& u, const Vector& v) {
        if (abs((u - minp) % (v - minp)) < EPS) {
            return (u - minp).sqlen() < (v - minp).sqlen();
        }
        return (u - minp) % (v - minp) < 0;
    });

    bool online = true;
    for (int i = 2; i < n; ++i) {
        online &= abs((p[i] - p[0]) % (p[i] - p[1])) < EPS;
    }
    if (online) {
        sort(p.begin(), p.end(), [&](const Vector& u, const Vector& v) {
            return (u - minp).sqlen() < (v - minp).sqlen();
        });
        vector<Vector> st = {p[0], p.back()};
        p.pop_back();
        reverse(p.begin(), p.end());
        p.pop_back();
        return st;
    }

    p.push_back(p[0]);
    /**for (auto elem : p) {
        cout << (double)elem.x << " " << (double)elem.y << " : ";
    }
    cout << endl;*/
    vector<Vector> st;
    int sz = 0;
    vector<Vector> p1;
    for (auto v : p) {
        while (sz >= 2 && (st[sz - 1] - st[sz - 2]) % (v - st[sz - 1]) >= -EPS) {
            p1.push_back(st.back());
            st.pop_back();
            --sz;
        }
        st.push_back(v);
        ++sz;
    }
    st.pop_back();
    p = p1;
    return st;
}

vector<Vector> get_bst(const Vector& dir, const vector<Vector>& p, int cnt) {
    if (p.empty()) return p;
    int n = p.size();
    int k = 0;
    while ((1 << k) < n) ++k;
    int i = 0;
    while (k >= 0) {
        int i1 = (i + (1 << k)) % n;
        int i2 = (i - (1 << k) + 2 * n) % n;
        if (dir * p[i1] > dir * p[i]) i = i1;
        if (dir * p[i2] > dir * p[i]) i = i2;
        --k;
    }
    vector<Vector> ans = {p[i]};
    int sz = min(cnt - 1, n - 1);
    int t1 = (i + 1) % n;
    int t2 = (i - 1 + n) % n;
    for (int _ = 0; _ < sz; ++_) {
        if (dir * p[t1] > dir * p[t2]) {
            ans.push_back(p[t1]);
            t1 = (t1 + 1) % n;
        } else {
            ans.push_back(p[t2]);
            t2 = (t2 - 1 + n) % n;
        }
    }
    return ans;
}

mt19937 rnd;
const int MAX = 100000000;

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cout << fixed << setprecision(10);
    
    int n;
    cin >> n;
    vector<IVector> p(n);
    int cnt0 = 0;
    for (int i = 0; i < n; ++i) {
        cin >> p[i];
        /**p[i].x = rnd() % (2 * MAX) - MAX;
        p[i].y = rnd() % (2 * MAX) - MAX;*/
    }
    vector<IVector> p1;
    for (int i = 0; i < n; ++i) {
        if (p[i] == IVector()) {
            ++cnt0;
        } else {
            p1.push_back(p[i]);
        }
    }
    p = p1;
    n = p.size();

    int q;
    cin >> q;
    vector<pair<IVector, int>> qu(q);
    for (int i = 0; i < q; ++i) {
        cin >> qu[i].first >> qu[i].second;
        /**qu[i].first.x = rnd() % (2 * MAX) - MAX;
        qu[i].first.y = rnd() % (2 * MAX) - MAX;
        qu[i].second = 5;*/
        qu[i].second -= cnt0;
    }

    int cnt = 0;
    for (int i = 0; i < n; ++i) {
        if (hp(p[i])) ++cnt;
    }
    vector<pair<IVector, int>> ev;
    for (int i = 0; i < n; ++i) {
        ev.push_back({p[i], -1});
        ev.push_back({-p[i], q});
    }
    for (int i = 0; i < q; ++i) {
        if (qu[i].first == IVector()) {
            is_bad[i] = true;
            continue;
        }
        ev.push_back({{qu[i].first.y, -qu[i].first.x}, i});
    }
    sort(ev.begin(), ev.end());
    for (auto elem : ev) {
        if (elem.second == -1) {
            --cnt;
        } else if (elem.second == q) {
            ++cnt;
        } else {
            if (cnt < qu[elem.second].second) {
                is_bad[elem.second] = true;
            }
        }
    }

    vector<Vector> pv;
    for (int i = 0; i < n; ++i) {
        pv.push_back(Vector(p[i], true));
        /// cerr << i << ": " << (double)pv[i].x << " " << (double)pv[i].y << endl;
    }
    vector<vector<Vector>> hulls;
    for (int i = 0; i < MAXK; ++i) {
        hulls.push_back(convex(pv));
        /**for (Vector v : hulls.back()) {
            cout << (double)v.x << " " << (double)v.y << "; ";
        }
        cout << endl;*/
    }
    for (int i = 0; i < q; ++i) {
        if (is_bad[i]) {
            cout << "-1\n";
            continue;
        }
        if (qu[i].second <= 0) {
            cout << "0\n";
            continue;
        }
        int k = qu[i].second;
        Vector dir = qu[i].first;
        vector<Vector> bst;
        for (int i = 0; i < k; ++i) {
            auto res = get_bst(dir, hulls[i], k - i);
            /**vector<Vector> bst1;
            int f1 = 0, f2 = 0;
            for (int i = 0; i <= k && i < (int)bst.size() + res.size(); ++i) {
                if (f2 >= res.size()) {
                    bst1.push_back(bst[f1++]);
                } else if (f1 >= bst.size()) {
                    bst1.push_back(res[f2++]);
                } else if (bst[f1] * dir > res[f2] * dir) {
                    bst1.push_back(bst[f1++]);
                } else {
                    bst1.push_back(res[f2++]);
                }
            }
            bst = move(bst1);*/
            for (auto elem : res) {
                bst.push_back(elem);
                for (int i = (int)bst.size() - 1; i > 0; --i) {
                    if (dir * bst[i] > dir * bst[i - 1]) {
                        swap(bst[i], bst[i - 1]);
                    } else {
                        break;
                    }
                }
                if ((int)bst.size() > k) bst.pop_back();
            }
        }
        long double ans = dir * bst[k - 1];
        /// cout << (double)bst[k - 1].x << " " << (double)bst[k - 1].y << endl;
        ans /= sqrtl(dir.x * dir.x + dir.y * dir.y);
        ans = 0.5 / ans;
        cout << ans << "\n";
        if (ans < -1) {
            cout << n << "\n";
            for (int i = 0; i < n; ++i) {
                cout << p[i].x << " " << p[i].y << "\n";
            }
            cout << qu[i].first.x << " " << qu[i].first.y << " " << qu[i].second << endl;
            return 0;
        }
    }



    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

5
5 -3
5 4
-6 2
-5 0
4 1
2
-3 -10 1
6 -9 1

output:

8.7002554241
3.2260195623

result:

ok 2 numbers

Test #2:

score: 0
Accepted
time: 0ms
memory: 3840kb

input:

8
4 -1
4 -8
0 9
4 -7
-5 -2
5 -5
7 5
-9 2
10
4 -8 1
7 -7 5
-10 8 2
-9 9 2
4 -7 5
-1 -10 2
6 -3 2
2 -9 3
-10 -10 1
5 9 1

output:

3.1677629681
26.1629509039
5.4614883202
6.3639610307
-1
5.2894082216
3.7267799625
4.6097722286
2.9294423792
4.7617289402

result:

ok 10 numbers

Test #3:

score: 0
Accepted
time: 0ms
memory: 4068kb

input:

5
-4 -7
5 0
2 4
-7 -7
4 4
20
0 -5 2
-4 -7 2
-7 7 3
4 -4 3
-7 4 3
4 -4 1
2 4 1
6 -7 2
4 -4 2
4 4 3
5 4 1
-1 9 2
8 9 3
4 -4 2
6 3 3
-10 -3 2
-7 7 1
9 -4 1
-4 -7 3
-2 0 2

output:

7.0000000000
5.1305276580
-1
-1
-1
3.5355339059
2.2360679775
11.9854077945
15.3206469257
3.5355339059
2.4627400913
4.5276925691
3.7629983059
15.3206469257
2.9814239700
5.6217035048
7.0710678119
2.7357938338
-1
8.1250000000

result:

ok 20 numbers

Test #4:

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

input:

100
63 -48
20 -62
-81 -31
-17 -93
2 -74
72 25
-71 37
-71 17
56 67
-47 65
-89 14
62 30
-71 -33
14 -53
-57 -52
30 80
-14 -69
-45 -19
-54 -71
58 -20
-57 12
5 -56
-76 -2
26 61
24 60
10 -97
-63 38
17 81
-43 -38
44 35
-86 37
62 72
77 11
41 29
14 81
77 55
-54 -33
-43 -51
76 14
55 47
43 24
69 -13
16 75
11 9...

output:

26.7586788688
29.5714059979
24.6221445045
27.7717456547
26.6783667129
24.4237024605
28.8933481964
29.7761695578
31.9403629705
27.2149016024
31.7280950457
27.0711605517
25.2991100306
26.8710651521
28.9958394534
28.3563142462
29.9872588920
25.6496237196
25.1496681332
28.3011569706
28.6117519545
26.690...

result:

ok 100 numbers

Test #5:

score: -100
Wrong Answer
time: 166ms
memory: 5856kb

input:

10000
-3 3
-6 2
-4 1
-2 -5
5 -6
-7 -2
0 7
1 -4
8 0
-4 4
-6 -2
5 0
2 9
-4 -8
0 -8
7 4
-7 2
3 3
4 1
-1 7
-4 -2
6 0
3 -5
-7 2
0 -9
7 0
7 3
-6 0
1 7
6 2
2 -9
1 8
3 -3
2 -9
4 2
4 -5
6 0
-3 6
7 3
0 8
0 -4
7 0
-5 8
5 -5
-5 -1
0 9
-4 -3
-9 -1
7 -2
-7 -2
4 0
-6 6
-3 4
6 7
2 5
-8 -5
0 5
4 0
0 -4
0 -6
-5 3
-5 ...

output:

2.3323807579
2.3584952830
6.3245553203
2.2360679775
4.4721359550
2.2360679775
3.0103986447
2.8284271247
2.0275875101
2.1886350671
2.3035022138
8.2462112512
3.8873012632
2.0000000000
2.8284271247
3.7735924528
6.3245553203
14.1421356237
2.1081851068
4.0311288741
2.8284271247
inf
2.8284271247
7.2801098...

result:

wrong answer 1st numbers differ - expected: '2.1549170', found: '2.3323808', error = '0.0823529'