QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#368185 | #5570. Epidemic Escape | APJifengc | WA | 328ms | 6848kb | C++14 | 3.7kb | 2024-03-26 21:41:39 | 2024-03-26 21:41:40 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100005;
const double eps = 1e-11;
int n, q, x[MAXN], y[MAXN];
pair<double, double> pt[MAXN];
bool vis[MAXN];
struct Convex {
int stk1[MAXN], top1;
int stk2[MAXN], top2;
double cross(int i, int j, int k) {
return (pt[j].first - pt[i].first) * (pt[k].second - pt[i].second)
- (pt[k].first - pt[i].first) * (pt[j].second - pt[i].second);
}
void build() {
for (int i = 1; i <= n; i++) if (!vis[i]) {
while (top1 > 1 && cross(stk1[top1 - 1], stk1[top1], i) >= -eps) top1--;
stk1[++top1] = i;
}
for (int i = 1; i <= n; i++) if (!vis[i]) {
while (top2 > 2 && cross(stk2[top2 - 1], stk2[top2], i) <= eps) top2--;
stk2[++top2] = i;
}
for (int i = 1; i <= top1; i++) vis[stk1[i]] = 1;
for (int i = 1; i <= top2; i++) vis[stk2[i]] = 1;
}
vector<int> query(double cos, double sin) {
if (!top1) return {};
vector<int> ret;
for (int i = 1; i <= min(5, top1); i++) ret.push_back(stk1[i]);
for (int i = 1; i <= min(5, top2); i++) ret.push_back(stk2[i]);
for (int i = max(1, top1 - 4); i <= top1; i++) ret.push_back(stk1[i]);
for (int i = max(1, top2 - 4); i <= top2; i++) ret.push_back(stk2[i]);
if (sin >= 0) {
int l = 1, r = top1;
while (l < r - 2) {
int mid1 = (l + r) >> 1, mid2 = mid1 + 1;
if (pt[stk1[mid1]].first * cos + pt[stk1[mid1]].second * sin
< pt[stk1[mid2]].first * cos + pt[stk1[mid2]].second * sin) {
l = mid1;
} else {
r = mid2;
}
}
for (int i = max(1, l - 4); i <= min(r + 4, top1); i++) ret.push_back(stk1[i]);
} else {
int l = 1, r = top2;
while (l < r - 2) {
int mid1 = (l + r) >> 1, mid2 = mid1 + 1;
if (pt[stk2[mid1]].first * cos + pt[stk2[mid1]].second * sin
< pt[stk2[mid2]].first * cos + pt[stk2[mid2]].second * sin) {
l = mid1;
} else {
r = mid2;
}
}
for (int i = max(1, l - 4); i <= min(r + 4, top2); i++) ret.push_back(stk2[i]);
}
sort(ret.begin(), ret.end());
ret.erase(unique(ret.begin(), ret.end()), ret.end());
return ret;
}
} convex[6];
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
scanf("%d%d", &x[i], &y[i]);
long long p = 1ll * x[i] * x[i] + 1ll * y[i] * y[i];
pt[i] = { 2.0 * x[i] / p, 2.0 * y[i] / p };
}
sort(pt + 1, pt + 1 + n);
for (int i = 1; i <= 5; i++) convex[i].build();
scanf("%d", &q);
while (q--) {
int x, y, k; scanf("%d%d%d", &x, &y, &k);
if (x == 0 && y == 0) {
printf("-1\n");
continue;
}
double d = sqrt(1ll * x * x + 1ll * y * y);
double c = x / d, s = y / d;
vector<int> p;
for (int i = 1; i <= 5; i++) {
for (int j : convex[i].query(c, s)) p.push_back(j);
}
sort(p.begin(), p.end());
p.erase(unique(p.begin(), p.end()), p.end());
vector<double> ans;
for (int i : p) ans.push_back(c * pt[i].first + s * pt[i].second);
sort(ans.begin(), ans.end(), greater<>());
if (ans.size() < k || ans[k - 1] < eps) printf("-1\n");
else printf("%.12lf\n", 1 / ans[k - 1]);
}
return 0;
}
/*
5
5 -3
5 4
-6 2
-5 0
4 1
2
-3 -10 1
6 -9 1
*/
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 5808kb
input:
5 5 -3 5 4 -6 2 -5 0 4 1 2 -3 -10 1 6 -9 1
output:
8.700255424092 3.226019562257
result:
ok 2 numbers
Test #2:
score: 0
Accepted
time: 1ms
memory: 5852kb
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.167762968125 26.162950903902 5.461488320163 6.363961030679 -1 5.289408221643 3.726779962500 4.609772228646 2.929442379201 4.761728940206
result:
ok 10 numbers
Test #3:
score: 0
Accepted
time: 1ms
memory: 5864kb
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.000000000000 5.130527658008 -1 -1 -1 3.535533905933 2.236067977500 11.985407794481 15.320646925709 3.535533905933 2.462740091320 4.527692569069 3.762998305873 15.320646925709 2.981423970000 5.621703504798 7.071067811865 2.735793833832 -1 8.125000000000
result:
ok 20 numbers
Test #4:
score: 0
Accepted
time: 1ms
memory: 5996kb
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.758678868757 29.571405997862 24.622144504490 27.771745654731 26.678366712897 24.423702460472 28.893348196396 29.776169557758 31.940362970515 27.214901602378 31.728095045748 27.071160551681 25.299110030617 26.871065152125 28.995839453428 28.356314246198 29.987258891963 25.649623719567 25.149668133...
result:
ok 100 numbers
Test #5:
score: 0
Accepted
time: 30ms
memory: 5956kb
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.154917004617 2.167265935743 2.067643085495 2.111841978750 2.111841978750 2.111841978750 2.124987278610 2.121320343560 2.027587510099 2.092882282882 2.141537214392 2.061552812809 2.154917004617 2.000000000000 2.121320343560 2.167265935743 2.067643085495 2.020305089104 2.067643085495 2.141537214392 ...
result:
ok 10000 numbers
Test #6:
score: 0
Accepted
time: 32ms
memory: 5912kb
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.302375937283 481.662711989051 792.185075601819 579.954261849271 807.709446267824 242.592175484557 882.267514766716 530.780780259742 664.182175961040 796.360739767517 662.707167898653 639.072619278744 125.821182715263 745.729175266719 732.496721810003 676.532780148248 808.996411868281 427.9627407...
result:
ok 10000 numbers
Test #7:
score: 0
Accepted
time: 328ms
memory: 6444kb
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.497776332413 1193.960228745125 1171.242726187060 1856.289036299031 2681.882945853974 1170.870740836293 1128.361471572153 1855.878337989197 3518.324147970210 1541.786008215450 1515.015122316481 1124.406566046596 2146.716711313768 1179.430678947101 1164.158878271529 1251.511082908229 2737.3506509...
result:
ok 100000 numbers
Test #8:
score: -100
Wrong Answer
time: 204ms
memory: 6848kb
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.006104245782 58915321.852980069816 50023261.546197578311 113036174.949005439878 78034088.229483500123 53859500.251401767135 61701178.312288112938 68727580.875053539872 259323938.656887203455 124799835.526553139091 64028884.891321368515 51019589.744483724236 50191011.256984151900 257091491.6...
result:
wrong answer 1st numbers differ - expected: '49999995.0818662', found: '72525271.0061042', error = '0.4505056'