QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#368221#5570. Epidemic EscapeAPJifengcWA 443ms9180kbC++143.7kb2024-03-26 22:07:552024-03-26 22:07:56

Judging History

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

  • [2024-03-26 22:07:56]
  • 评测
  • 测评结果:WA
  • 用时:443ms
  • 内存:9180kb
  • [2024-03-26 22:07:55]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100005;
const long double eps = 1e-18;
int n, q, x[MAXN], y[MAXN];
pair<long double, long double> pt[MAXN];
bool vis[MAXN];
struct Convex {
    int stk1[MAXN], top1;
    int stk2[MAXN], top2;
    long 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(long double cos, long 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() {
    // freopen("E.in", "r", stdin);
    // freopen("E.out", "w", stdout);
    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.0l * x[i] / p, 2.0l * 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;
        }
        long double d = sqrtl(1ll * x * x + 1ll * y * y);
        long 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<long 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;
}

详细

Test #1:

score: 100
Accepted
time: 1ms
memory: 5956kb

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: 7964kb

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: 5872kb

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: 5900kb

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.299110030618
26.871065152125
28.995839453428
28.356314246198
29.987258891963
25.649623719567
25.149668133...

result:

ok 100 numbers

Test #5:

score: 0
Accepted
time: 47ms
memory: 6256kb

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: 42ms
memory: 8292kb

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.185075601818
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: 443ms
memory: 9180kb

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.497776332412
1193.960228745125
1171.242726187060
1856.289036299031
2681.882945853974
1170.870740836293
1128.361471572153
1855.878337989197
3518.324147970211
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: 239ms
memory: 8744kb

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.006104241926
58915321.852980080141
50023261.546197589421
113036174.949005437622
78034088.229483501018
53859500.251401771802
61701178.312288114292
68727580.875053559772
259323938.656887213074
124799835.526553151016
64028884.891321375693
51019589.744483725706
50191011.256984152984
257091491.6...

result:

wrong answer 1st numbers differ - expected: '49999995.0818662', found: '72525271.0061042', error = '0.4505056'