QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#81938 | #5570. Epidemic Escape | ckiseki | WA | 403ms | 11468kb | C++20 | 6.9kb | 2023-02-26 18:46:34 | 2023-02-26 18:46:37 |
Judging History
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-9;
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) / (2 * (co * X + si * 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) / (2 * (co * X + si * 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) / (2 * (co * X + si * 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: 1ms
memory: 3500kb
input:
5 5 -3 5 4 -6 2 -5 0 4 1 2 -3 -10 1 6 -9 1
output:
8.70025542409212556370 3.22601956225725382504
result:
ok 2 numbers
Test #2:
score: 0
Accepted
time: 2ms
memory: 3648kb
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.16776296812470222353 26.16295090390225843574 5.46148832016331198290 6.36396103067892759996 -1.00000000000000000000 5.28940822164257365553 3.72677996249964967501 4.60977222864644353706 2.92944237920141128083 4.76172894020648787040
result:
ok 10 numbers
Test #3:
score: 0
Accepted
time: 0ms
memory: 3656kb
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.98540779448075319774 15.32064692570853074206 3.53553390593273786369 2.46274009132032635798 4.52769256906870865009 3.76299830587259243...
result:
ok 20 numbers
Test #4:
score: 0
Accepted
time: 0ms
memory: 3524kb
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.75867886875729278508 29.57140599786168759858 24.62214450449026159617 27.77174565473063905414 26.67836671289651183543 24.42370246047215866757 28.89334819639630655072 29.77616955775845801989 31.94036297051516799100 27.21490160237786040849 31.72809504574849922241 27.07116055168118597812 25.299110030...
result:
ok 100 numbers
Test #5:
score: 0
Accepted
time: 69ms
memory: 4072kb
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.12498727861040513708 2.12132034355964253325 2.02758751009940644638 2.09288228288167208455 2.14153721439180211306 2.06155281280883029282 2.15491700461674157868 2...
result:
ok 10000 numbers
Test #6:
score: 0
Accepted
time: 69ms
memory: 4032kb
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.18507560181844529001 579.95426184927105295319 807.70944626782362263384 242.59217548455711094268 882.26751476671616125635 530.78078025974182307944 664.18217596104034106119 796.36073976751670477903 662.70716789865299439777 639.07261927874403351080 ...
result:
ok 10000 numbers
Test #7:
score: 0
Accepted
time: 403ms
memory: 11468kb
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.49777633241239471751 1193.96022874512525902002 1171.24272618705981330312 1856.28903629903057437289 2681.88294585397401315063 1170.87074083629289122932 1128.36147157215272196495 1855.87833798919717853693 3518.32414797021063068705 1541.78600821544991661405 1515.01512231648063411260 1124.406566046...
result:
ok 100000 numbers
Test #8:
score: -100
Wrong Answer
time: 328ms
memory: 10952kb
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.00610423853504471481 58910687.43728349222874385305 50023261.54619758813714724965 113047042.35530966673104558140 78022286.43956936563336057588 53859500.25140177321009105071 61701178.31228811781329568475 68727580.87505355239409254864 259323938.65688721874903421849 124799835.526553145107754971...
result:
wrong answer 1st numbers differ - expected: '49999995.0818662', found: '72525271.0061042', error = '0.4505056'