QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#368187 | #5570. Epidemic Escape | APJifengc | WA | 1ms | 7904kb | C++14 | 3.7kb | 2024-03-26 21:43:12 | 2024-03-26 21:43:12 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100005;
const double eps = 0;
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
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 7904kb
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: 0ms
memory: 5804kb
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: -100
Wrong Answer
time: 1ms
memory: 5860kb
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 inf inf 72057594037927936.000000000000 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:
wrong output format Expected double, but "inf" found