QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#353684#6426. Interested in SkiingPorNPtreeWA 9ms3952kbC++142.4kb2024-03-14 14:54:072024-03-14 14:54:08

Judging History

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

  • [2024-03-14 14:54:08]
  • 评测
  • 测评结果:WA
  • 用时:9ms
  • 内存:3952kb
  • [2024-03-14 14:54:07]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

const int N = 105;

int n, a[N], b[N], c[N], d[N];
pair<int, int> pr[N * 2];
double f[N * 2];
mt19937 rnd;

int ins(double a, double b, double c, double d, double e, double f, double g, double h)
{
    a += (double)rnd() / 1e16, b += (double)rnd() / 1e16, c += (double)rnd() / 1e16, d += (double)rnd() / 1e16;
    e += (double)rnd() / 1e16, f += (double)rnd() / 1e16, g += (double)rnd() / 1e16, h += (double)rnd() / 1e16;
    double k1 = (d - b) / (c - a), b1 = b - k1 * a;
    double k2 = (h - f) / (g - e), b2 = f - k2 * e;
    double ix = (b2 - b1) / (k1 - k2), iy = k1 * ix + b1;
    return ix > min(a, c) - 1e-2 && ix < max(a, c) + 1e-2 && ix > min(e, g) - 1e-2 && ix < max(e, g) + 1e-2 && iy > min(b, d) - 1e-2 && iy < max(b, d) + 1e-2 && iy > min(f, h) - 1e-2 && iy < max(f, h) + 1e-2 && fabs(ix - a) + fabs(iy - b) > 1e-2 && fabs(ix - c) + fabs(iy - d) > 1e-2 && fabs(ix - e) + fabs(iy - f) > 1e-2 && fabs(ix - g) + fabs(iy - h) > 1e-2;
}

int check(double a, double b, double c, double d)
{
    for (int i = 1; i <= n; ++i) {
        if (ins(a, b, c, d, ::a[i], ::b[i], ::c[i], ::d[i])) {
            return 0;
        }
    }
    return 1;
}

signed main()
{
    int m, V;
    scanf("%d%d%d", &n, &m, &V);
    for (int i = 1; i <= n; ++i) {
        scanf("%d%d%d%d", &a[i], &b[i], &c[i], &d[i]);
        pr[i * 2 - 1] = make_pair(b[i], a[i]);
        pr[i * 2] = make_pair(d[i], c[i]);
    }
    sort(pr + 1, pr + n + n + 1);
    if (check(0, -20000, 0, 20000)) {
        puts("0");
        return 0;
    }
    double res = 1e10;
    for (int i = 1; i <= n + n; ++i) {
        f[i] = 1e10;
        if (pr[i].second <= -m || pr[i].second >= m) {
            continue;
        }
        if (check(pr[i].second, -20000, pr[i].second, pr[i].first)) {
            f[i] = 0;
        } else {
            for (int j = 1; j < i; ++j) {
                if (pr[i].first != pr[j].first && check(pr[j].second, pr[j].first, pr[i].second, pr[i].first)) {
                    f[i] = min(f[i], max(f[j], fabs((double)(pr[i].second - pr[j].second) / (pr[i].first - pr[j].first))));
                }
            }
        }
        if (check(pr[i].second, pr[i].first, pr[i].second, 20000)) {
            res = min(res, f[i]);
        }
    }
    if (res > 5e9) {
        puts("-1");
    } else {
        printf("%.10lf\n", res * V);
    }
    return 0;
}

詳細信息

Test #1:

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

input:

3 2 1
-2 0 1 0
-1 4 2 4
0 1 0 3

output:

1.0000000000

result:

ok found '1.0000000', expected '1.0000000', error '0.0000000'

Test #2:

score: 0
Accepted
time: 0ms
memory: 3560kb

input:

2 1 2
-1 0 1 0
1 1 0 1

output:

-1

result:

ok found '-1.0000000', expected '-1.0000000', error '-0.0000000'

Test #3:

score: 0
Accepted
time: 1ms
memory: 3944kb

input:

2 3 7
-3 0 2 2
3 1 -2 17

output:

1.8666666667

result:

ok found '1.8666667', expected '1.8666667', error '0.0000000'

Test #4:

score: 0
Accepted
time: 1ms
memory: 3828kb

input:

1 100 1
-100 0 99 0

output:

0.0000000000

result:

ok found '0.0000000', expected '0.0000000', error '-0.0000000'

Test #5:

score: 0
Accepted
time: 1ms
memory: 3908kb

input:

3 8 3
-8 -9 0 -9
-6 -6 6 6
8 9 0 9

output:

6.0000000000

result:

ok found '6.0000000', expected '6.0000000', error '0.0000000'

Test #6:

score: 0
Accepted
time: 0ms
memory: 3928kb

input:

3 8 3
-8 9 0 9
-6 6 6 -6
8 -9 0 -9

output:

6.0000000000

result:

ok found '6.0000000', expected '6.0000000', error '0.0000000'

Test #7:

score: 0
Accepted
time: 1ms
memory: 3848kb

input:

2 1 2
-1 0 0 0
1 1 0 1

output:

0

result:

ok found '0.0000000', expected '0.0000000', error '-0.0000000'

Test #8:

score: 0
Accepted
time: 1ms
memory: 3944kb

input:

3 9 10
-9 -26 0 -8
-6 -6 6 6
9 26 0 8

output:

30.0000000000

result:

ok found '30.0000000', expected '30.0000000', error '0.0000000'

Test #9:

score: 0
Accepted
time: 1ms
memory: 3952kb

input:

3 9 10
-9 26 0 8
-6 6 6 -6
9 -26 0 -8

output:

30.0000000000

result:

ok found '30.0000000', expected '30.0000000', error '0.0000000'

Test #10:

score: 0
Accepted
time: 0ms
memory: 3888kb

input:

4 9 5
-9 -4 -3 0
-6 2 6 2
-6 -6 2 -8
-4 -12 9 -25

output:

7.5000000000

result:

ok found '7.5000000', expected '7.5000000', error '0.0000000'

Test #11:

score: 0
Accepted
time: 9ms
memory: 3932kb

input:

100 10000 2
1663 -5179 1091 -542
-5687 -1048 7838 4346
3959 -2780 1099 -9402
-8661 -856 3945 7651
-1688 5290 -3518 2625
10000 -8028 5857 -9678
-9929 4601 -6350 3819
-1173 -9608 -2422 -9939
10000 -4668 5423 -2597
-572 -9335 -5787 -7658
-10000 1589 3117 9331
9818 4874 1345 1669
9026 -8243 2952 -6411
8...

output:

5.9776075427

result:

ok found '5.9776075', expected '5.9776075', error '0.0000000'

Test #12:

score: 0
Accepted
time: 1ms
memory: 3912kb

input:

20 100 5
100 55 77 -18
60 -33 45 -1
41 41 -84 53
66 -77 30 -70
44 -15 -45 -98
-36 19 67 29
51 -71 89 -50
100 -48 92 -39
43 20 -22 -33
10 -71 7 -52
-100 -9 -4 13
-100 90 -19 81
73 67 6 54
-86 2 -91 67
59 -35 77 -55
-43 -40 -58 -41
100 82 -39 55
40 -17 39 -12
42 4 84 -52
61 78 -46 86

output:

27.0000000000

result:

ok found '27.0000000', expected '27.0000000', error '0.0000000'

Test #13:

score: 0
Accepted
time: 1ms
memory: 3932kb

input:

20 100 1
90 -37 -90 90
-61 46 -83 42
26 -45 -89 -79
-100 -3 -51 -34
40 -57 22 -70
90 55 17 75
5 -50 -35 24
-1 -20 33 -19
-69 78 100 -13
-45 -52 -89 -15
100 -100 -3 -23
49 84 78 95
-48 43 -21 -23
100 53 78 84
65 -42 84 -61
100 23 100 19
-58 38 -48 18
26 -53 -51 -92
29 37 -81 90
-5 82 43 30

output:

1.3181818182

result:

ok found '1.3181818', expected '1.3181818', error '0.0000000'

Test #14:

score: -100
Wrong Answer
time: 6ms
memory: 3828kb

input:

100 10000 9
9893 -5 -4023 94
2920 -32 -2174 -97
7462 24 4169 40
-6157 -25 -6492 40
5908 -16 647 48
4128 -19 -5163 -5
4082 96 7645 37
-8896 29 -2485 59
165 1 -1634 59
7644 -64 6345 -96
-8569 46 -5850 72
-2219 -64 -5429 -13
641 -36 -3923 -25
-1947 6 -3957 43
8241 -6 -2456 77
5268 -95 890 -75
3296 78 -...

output:

1898.0526315789

result:

wrong answer 1st numbers differ - expected: '3037.1538462', found: '1898.0526316', error = '0.3750555'