QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#82546#5570. Epidemic EscapeckisekiRE 0ms0kbC++7.7kb2023-02-28 01:13:072023-02-28 01:13:07

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 01:13:07]
  • 评测
  • 测评结果:RE
  • 用时:0ms
  • 内存:0kb
  • [2023-02-28 01:13:07]
  • 提交

answer

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

#ifdef local
#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 = __float128;
// using LLF = long double;

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 = 1 / LLF(1e20);

// LLF abs(LLF x) {
//     return x > 0 ? x : -x;
// }

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

namespace std {

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

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

    LLF d = sqrtl(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);
    debug(fixed, setprecision(15));
    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);
            debug(p.back().x, p.back().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);
    }

    {
        ofstream fout("cvs.txt");
        int m = cvs.size();
        int c = m - 1;
        for (auto cv: cvs) {
            for (auto pt: cv)
                fout << fixed << setprecision(20)
                    << pt.x << ' ' << pt.y << ' ' << c << '\n';
            for (auto pt: cv)
                debug(pt.x, pt.y, pt.id);
            --c;
        }
    }

    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) / aa >= eps) {
        //     debug(abs(ans - aa));
        //     cout << x << ' ' << y << ' ' << k << endl;
        //     cout << ans << ' ' << aa << endl;
        //     assert (false);
        // }
        cout << fixed << setprecision(20) << ans << '\n';
    }

    return 0;
}

详细

Test #1:

score: 0
Dangerous Syscalls

input:

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

output:


result: