QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#82546 | #5570. Epidemic Escape | ckiseki | RE | 0ms | 0kb | C++ | 7.7kb | 2023-02-28 01:13:07 | 2023-02-28 01:13:07 |
Judging History
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;
}
Details
Tip: Click on the bar to expand more detailed information
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