QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#368187#5570. Epidemic EscapeAPJifengcWA 1ms7904kbC++143.7kb2024-03-26 21:43:122024-03-26 21:43:12

Judging History

你现在查看的是最新测评结果

  • [2024-03-26 21:43:12]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:7904kb
  • [2024-03-26 21:43:12]
  • 提交

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