QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#82538#5570. Epidemic EscapeckisekiWA 446ms10996kbC++7.1kb2023-02-28 00:52:082023-02-28 00:52:11

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-02-28 00:52:11]
  • 评测
  • 测评结果:WA
  • 用时:446ms
  • 内存:10996kb
  • [2023-02-28 00:52:08]
  • 提交

answer

#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>

#ifdef CKISEKI
#define safe cerr<<__PRETTY_FUNCTION__<<" line "<<__LINE__<< " safe\n"
#define debug(a...) qwerty(#a, a)
#define orange(a...) dvorak(#a, a)
using std::cerr;
template <typename ...T>
void qwerty(const char *s, T ...a) {
    cerr << "\e[1;32m(" << s << ") = (";
    int cnt = sizeof...(T);
    (..., (cerr << a << (--cnt ? ", " : ")\e[0m\n")));
}
template <typename Iter>
void dvorak(const char *s, Iter L, Iter R) {
    cerr << "\e[1;32m[ " << s << " ] = [ ";
    for (int f = 0; L != R; ++L)
        cerr << (f++ ? ", " : "") << *L;
    cerr << " ]\e[0m\n";
}
#else
#define safe ((void)0)
#define debug(...) safe
#define orange(...) safe
#endif

#define all(v) begin(v),end(v)
using namespace std;

using LLF = long double;

//LLF abs(const LLF &x) { return x < 0 ? -x : x; }

struct Point {
    LLF x, y;
    int id;
    Point(LLF &&t_x, LLF &&t_y, int t_id) : x(t_x), y(t_y), id(t_id) {}
};

Point operator-(const Point &lhs, const Point &rhs) {
    return Point(lhs.x - rhs.x, lhs.y - rhs.y, -1);
}
Point operator+(const Point &lhs, const Point &rhs) {
    return Point(lhs.x + rhs.x, lhs.y + rhs.y, -1);
}

LLF cross(const Point &lhs, const Point &rhs) {
    return lhs.x * rhs.y - lhs.y * rhs.x;
}
LLF dot(const Point &lhs, const Point &rhs) {
    return lhs.x * rhs.x + lhs.y * rhs.y;
}

const LLF eps = 1e-15;

int sgn(LLF x) {
    if (abs(x) < eps) return 0;
    return (x > 0) - (x < 0);
}

int ori(const Point &a, const Point &b, const Point &c) {
    return sgn(cross(b - a, c - a));
}

int Search(const vector<Point> &P, Point D) {
    if (P.empty()) return -1;
    // pair<LLF, int> best = {0, 0};
    // for (int i = 0; i < P.size(); ++i)
    //     best = max(best, {dot(D, P[i]), i});
    // return best.second;
    int p = 0;
    for (int s = 1<<__lg(P.size()); s; s >>= 1) {
        if (p + s < P.size() && dot(D, P[p + s - 1]) <= dot(D, P[p + s])) {
            p += s;
        }
    }
    return p;
}

ostream &operator<<(ostream &o, const __float128 &x) {
    return o << static_cast<long double>(x);
}
ostream &operator<<(ostream &o, const Point &p) {
    return o << '(' << p.x << ' ' << p.y << ')';
}
ostream &operator<<(ostream &o, pair<LLF, int> p) {
    return o << '{' << p.first << ',' << p.second << '}';
}

LLF brute(auto pts, int k, LLF x, LLF y) {
    if (x == 0 && y == 0) return -1;

    LLF d = sqrt(1LL*x*x+1LL*y*y);
    LLF co = x / d, si = y / d;
    vector<pair<LLF, int>> tm;
    for (int i = 0; i < pts.size(); i++) {
        auto [X, Y] = pts[i];
        if (X == 0 && Y == 0) {
            tm.emplace_back(0, i);
        } else if (x * X + y * Y > 0) {
            LLF t = (X * X + Y * Y) / (2 * (co * X + si * Y));
            tm.emplace_back(t, i);
        }
    }
    sort(tm.begin(), tm.end());
    orange(all(tm));
    safe;
    if (tm.size() < k) return -1;
    return tm[k - 1].first;
}

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int n;
    cin >> n;

    int zero = 0;
    vector<Point> p;
    vector<pair<int64_t,int64_t>> pts(n);
    for (int i = 0; i < n; i++) {
        auto &[x, y] = pts[i];
        cin >> x >> y;
        if (x == 0 && y == 0) {
            zero += 1;
        } else {
            p.emplace_back((2 * x) / LLF(x * x + y * y), (2 * y) / LLF(x * x + y * y), i);
        }
    }

    sort(p.begin(), p.end(), [](Point a, Point b) {
        return a.x < b.x;
    });

    vector<vector<Point>> cvs;

    vector<int> vis(n);
    for (int iter = 0; iter < 6; iter++) {
        vector<Point> upper, lower;
        for (int i = 0; i < p.size(); i++) {
            if (vis[p[i].id]) continue;
            while (upper.size() >= 2 && ori(upper.rbegin()[1], upper.back(), p[i]) <= 0)
                upper.pop_back();
            upper.emplace_back(p[i]);
            while (lower.size() >= 2 && ori(lower.rbegin()[1], lower.back(), p[i]) >= 0)
                lower.pop_back();
            lower.emplace_back(p[i]);
        }

        for (auto pt: upper)
            vis[pt.id] = true;
        for (auto pt: lower)
            vis[pt.id] = true;

        cvs.emplace_back(upper);
        cvs.emplace_back(lower);
    }

    safe;

    int q;
    cin >> q;
    while (q--) {
        int x, y, k;
        cin >> x >> y >> k;
        //auto aa = brute(pts, k, x, y);
        safe;
        auto solve = [&] () -> LLF {
            if (x == 0 && y == 0) {
                return -1;
            } else if (k <= zero) {
                return 0;
            } else {
                k -= zero;

                LLF d = sqrt(1LL*x*x+1LL*y*y);
                LLF co = x / d, si = y / d;
                Point dir(x / d, y / d, -1);
                debug(k, x, y, d, co, si);

                vector<pair<int,LLF>> tm;

                for (const auto &cv: cvs) {
                    int m = cv.size();
                    int idx = Search(cv, dir);
                    orange(all(cv));
                    debug(idx, k);

                    for (int j = max(0, idx-k); j <= idx + k && j < m; j++) {
                        auto [X, Y] = pts[cv[j].id];
                        if (x * X + y * Y > 0) {
                            LLF t = (X * X + Y * Y) * d / (2 * (x * X + y * Y));
                            debug(t, j);
                            tm.emplace_back(cv[j].id, t);
                        }
                    }
                    for (int j = 0; j < k && j < m; j++) {
                        auto [X, Y] = pts[cv[j].id];
                        if (x * X + y * Y > 0) {
                            LLF t = (X * X + Y * Y) * d / (2 * (x * X + y * Y));
                            debug(t, j);
                            tm.emplace_back(cv[j].id, t);
                        }
                    }
                    for (int j = m - 1; j >= 0 && j >= m - k; j--) {
                        auto [X, Y] = pts[cv[j].id];
                        if (x * X + y * Y > 0) {
                            LLF t = (X * X + Y * Y) * d / (2 * (x * X + y * Y));
                            debug(t, j);
                            tm.emplace_back(cv[j].id, t);
                        }
                    }
                }

                sort(tm.begin(), tm.end());

                vector<LLF> tt;

                for (size_t i = 0; i < tm.size(); i++) {
                    if (i == 0 || tm[i - 1].first != tm[i].first) {
                        tt.push_back(tm[i].second);
                    }
                }

                sort(tt.begin(), tt.end());
                orange(all(tt));
                if (tt.size() < k) {
                    return -1;
                } else {
                    return tt[k - 1];
                }
            }
        };

        auto ans = solve();
//        if (abs(ans - aa) >= eps) {
//            cout << x << ' ' << y << ' ' << k << endl;
//            cout << ans << ' ' << aa << endl;
//            assert (false);
//        }
        cout << fixed << setprecision(20) << ans << '\n';
    }

    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

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

output:

8.70025542409212556284
3.22601956225725382483

result:

ok 2 numbers

Test #2:

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

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.16776296812470222375
26.16295090390225843054
5.46148832016331198247
6.36396103067892759952
-1.00000000000000000000
5.28940822164257365553
3.72677996249964967501
4.60977222864644353706
2.92944237920141128083
4.76172894020648786997

result:

ok 10 numbers

Test #3:

score: 0
Accepted
time: 2ms
memory: 3564kb

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.13052765800816762930
-1.00000000000000000000
-1.00000000000000000000
-1.00000000000000000000
3.53553390593273786369
2.23606797749978980505
11.98540779448075319601
15.32064692570853074293
3.53553390593273786369
2.46274009132032635819
4.52769256906870865009
3.76299830587259243...

result:

ok 20 numbers

Test #4:

score: 0
Accepted
time: 3ms
memory: 3632kb

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.75867886875729278334
29.57140599786168760031
24.62214450449026159617
27.77174565473063905414
26.67836671289651183543
24.42370246047215866757
28.89334819639630655072
29.77616955775845801989
31.94036297051516799274
27.21490160237786040849
31.72809504574849922241
27.07116055168118597812
25.299110030...

result:

ok 100 numbers

Test #5:

score: 0
Accepted
time: 75ms
memory: 4328kb

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.15491700461674157868
2.16726593574273315788
2.06764308549470968808
2.11184197874980148250
2.11184197874980148250
2.11184197874980148250
2.12498727861040513729
2.12132034355964253325
2.02758751009940644638
2.09288228288167208477
2.14153721439180211306
2.06155281280883029282
2.15491700461674157868
2...

result:

ok 10000 numbers

Test #6:

score: 0
Accepted
time: 72ms
memory: 4108kb

input:

10000
-90174 318421
-37261 138897
-260388 -302590
-906833 35071
317743 -283220
390311 -85301
880987 325969
-315218 -116767
103089 -8223
-134988 -973121
-444593 229407
-552060 549321
265624 -337609
-264546 322379
28687 110143
467764 303005
-335748 32188
213125 274156
240105 751
-81255 -129323
148563 ...

output:

218.30237593728341800869
481.66271198905148168135
792.18507560181844523450
579.95426184927105295319
807.70944626782362263384
242.59217548455711095656
882.26751476671616125635
530.78078025974182307944
664.18217596104034111670
796.36073976751670483454
662.70716789865299439777
639.07261927874403351080
...

result:

ok 10000 numbers

Test #7:

score: 0
Accepted
time: 446ms
memory: 10868kb

input:

100000
-14593321 17388753
13488647 1223793
33907737 -8731155
-14502324 73522129
-13933178 -13752140
9462275 13349398
14636622 31405249
5160247 -69775840
-49415260 -40092130
-9926862 -25806124
14982829 -8025116
-5492901 4568113
48872077 86636033
19374632 32538501
-16657133 -11624530
-15398598 -966935...

output:

1331.49777633241239482853
1193.96022874512525902002
1171.24272618705981319209
1856.28903629903057448391
2681.88294585397401315063
1170.87074083629289111830
1128.36147157215272196495
1855.87833798919717864795
3518.32414797021063090909
1541.78600821544991650303
1515.01512231648063411260
1124.406566046...

result:

ok 100000 numbers

Test #8:

score: -100
Wrong Answer
time: 320ms
memory: 10996kb

input:

100000
-60674143 79489917
99210432 12541486
-99948887 -3196593
57015830 -82153478
10407645 99456921
-90320128 42921703
93983821 34161956
96773928 -25195355
69603194 71801068
27259746 -96212811
96031961 27890165
76618755 -64261689
-99095784 13417302
-95521354 -29591717
-34815155 -93743823
-93393132 -...

output:

72525271.00610423852776875719
58910687.43728349222874385305
50023261.54619758814078522846
113047042.35530966673104558140
78022286.43956936563336057588
53859500.25140177321372902952
61701178.31228811781693366356
68727580.87505355240136850625
259323938.65688721874903421849
124799835.526553145100479014...

result:

wrong answer 1st numbers differ - expected: '49999995.0818662', found: '72525271.0061042', error = '0.4505056'