QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#338300#5570. Epidemic Escapeucup-team1198#WA 0ms4080kbC++206.3kb2024-02-25 20:12:592024-02-25 20:12:59

Judging History

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

  • [2024-02-25 20:12:59]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:4080kb
  • [2024-02-25 20:12:59]
  • 提交

answer

#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 = long double;

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-18;

const int MAXK = 6;

vector<Vector> convex(vector<Vector>& p) {
    if (p.empty()) return p;
    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.sqlen() < v.sqlen();
        }
        return (u - minp) % (v - minp) < 0;
    });

    p.push_back(p[0]);
    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);
    }
    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;
}


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

    cout << fixed << setprecision(20);
    
    int n;
    cin >> n;
    vector<IVector> p(n);
    int cnt0 = 0;
    for (int i = 0; i < n; ++i) {
        cin >> p[i];
    }
    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].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));
    }
    vector<vector<Vector>> hulls;
    for (int i = 0; i < MAXK; ++i) {
        hulls.push_back(convex(pv));
    }
    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 + 1; ++i) {
            auto res = get_bst(dir, hulls[i], k - i + 1);
            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();
            }
        }
        double ans = dir * bst[k - 1];
        ans /= hypotl(dir.x, dir.y);
        ans = 0.5 / ans;
        cout << ans << "\n";
    }



    return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 4080kb

input:

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

output:

8.70025542409212526707
3.22601956225725361449

result:

ok 2 numbers

Test #2:

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

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.16776296812470192776
26.16295090390225652754
5.46148832016331198247
6.36396103067892848770
-1
5.28940822164257440363
3.72677996249964937903
4.60977222864644353706
2.92944237920141103970
4.76172894020648751479

result:

ok 10 numbers

Test #3:

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

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.00000000000000000000
5.13052765800816779063
-1
-1
-1
3.53553390593273775266
2.23606797749978980505
11.98540779448075355162
15.32064692570852848519
3.53553390593273775266
2.46274009132032656311
4.52769256906870776191
3.76299830587259265258
15.32064692570852848519
2.98142396999971959204
5.6217035047...

result:

ok 20 numbers

Test #4:

score: -100
Wrong Answer
time: 0ms
memory: 4044kb

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.75867886875729340090
37.08877778209946285415
34.67400402959466276798
37.45038790969758224492
29.32963329462993939956
30.21535040675885497308
44.43765437987656952146
40.84844147082198873022
31.94036297051517081513
27.55358415887123868515
31.84121384093657880499
27.07116055168118506913
42.142338615...

result:

wrong answer 2nd numbers differ - expected: '29.5714060', found: '37.0887778', error = '0.2542108'