QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#168720#6426. Interested in SkiingNOI_AK_MEAC ✓4ms5788kbC++141.8kb2023-09-08 20:36:572023-09-08 20:36:58

Judging History

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

  • [2023-09-08 20:36:58]
  • 评测
  • 测评结果:AC
  • 用时:4ms
  • 内存:5788kb
  • [2023-09-08 20:36:57]
  • 提交

answer

#pragma once
#pragma GCC optimize("Ofast, unroll-loops")
#include <bits/stdc++.h>
using namespace std;
typedef long double ld;
const int N = 100013;
const ld inf = 1e18;
int n, tt;
struct pt {
    int x, y;
    pt operator-(const pt &b)const {
        return{x - b.x, y - b.y};
    } bool operator<(const pt &b)const {
        return y < b.y;
    }
} p[N];
struct ln {
    pt x, y;
} l[N];
ld dp[N];
int sgn(int x) {
    return!x ? 0 : x > 0 ? 1 : -1;
}
int cr(pt x, pt y) {
    return x.x * y.y - x.y * y.x;
}
int f(pt a, pt b, pt c) {
    return cr(c - a, c - b);
}
bool isc(pt x, pt y, ln L) {
    return sgn(f(x, y, L.x)) * sgn(f(x, y, L.y)) < 0 && sgn(f(L.x, L.y, x)) * sgn(f(L.x, L.y, y)) < 0;
}
bool chk(pt x, pt y) {
    for (int i = 0; i < n; i++)
        if (isc(x, y, l[i]))
            return false;

    return true;
}
ld slp(pt x, pt y) {
    return fabsl((ld)(y.x - x.x) / (y.y - x.y));
}
int main() {
    cout << fixed << setprecision(15);
    int m, v;
    cin >> n >> m >> v;

    for (int i = 0, a, b, c, d; i < n; i++)
        cin >> a >> b >> c >> d, l[i] = {{a, b}, {c, d}}, p[tt++] = {a, b}, p[tt++] = {c, d};
    sort(p, p + tt);
    fill(dp, dp + tt, inf);
    ld ans = inf;

    if (chk({0, -10001}, {0, 10001}))
        ans = 0;

    for (int i = 0; i < tt; i++)
        if (abs(p[i].x) < m) {
            if (chk({p[i].x, -10001}, p[i]))
                dp[i] = 0;

            for (int j = 0; j < i; j++) {
                if (p[i].y == p[j].y)
                    break;

                if (chk(p[i], p[j]))
                    dp[i] = min(dp[i], max(dp[j], slp(p[i], p[j])));
            }

            if (chk({p[i].x, 10001}, p[i]))
                ans = min(ans, dp[i]);
        }

    if (ans > 1e17)
        cout << -1 << '\n';
    else
        cout << ans *v << '\n';
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 2ms
memory: 5732kb

input:

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

output:

1.000000000000000

result:

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

Test #2:

score: 0
Accepted
time: 2ms
memory: 5548kb

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: 0ms
memory: 5740kb

input:

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

output:

1.866666666666667

result:

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

Test #4:

score: 0
Accepted
time: 2ms
memory: 5680kb

input:

1 100 1
-100 0 99 0

output:

0.000000000000000

result:

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

Test #5:

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

input:

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

output:

6.000000000000000

result:

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

Test #6:

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

input:

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

output:

6.000000000000000

result:

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

Test #7:

score: 0
Accepted
time: 2ms
memory: 5708kb

input:

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

output:

0.000000000000000

result:

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

Test #8:

score: 0
Accepted
time: 2ms
memory: 5732kb

input:

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

output:

30.000000000000000

result:

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

Test #9:

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

input:

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

output:

30.000000000000000

result:

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

Test #10:

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

input:

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

output:

7.500000000000000

result:

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

Test #11:

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

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.977607542722451

result:

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

Test #12:

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

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.000000000000000

result:

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

Test #13:

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

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.318181818181818

result:

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

Test #14:

score: 0
Accepted
time: 3ms
memory: 5716kb

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:

3037.153846153846154

result:

ok found '3037.1538462', expected '3037.1538462', error '0.0000000'

Test #15:

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

input:

10 50 4
5 -45 22 -48
-50 20 -23 19
-43 -29 35 31
50 -33 40 48
-49 -32 0 -33
16 -50 21 -49
50 -38 -22 -18
-49 50 11 14
20 -23 16 -11
-27 -15 35 32

output:

3.354838709677419

result:

ok found '3.3548387', expected '3.3548387', error '0.0000000'

Test #16:

score: 0
Accepted
time: 2ms
memory: 5684kb

input:

10 50 1
-50 -3 28 -3
7 -30 2 -30
34 39 50 39
16 22 43 22
50 -32 7 -32
50 15 -2 15
-15 -42 24 -42
14 -26 28 -26
23 -10 -39 -10
50 -44 -31 -44

output:

1.666666666666667

result:

ok found '1.6666667', expected '1.6666667', error '0.0000000'

Test #17:

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

input:

10 50 2
35 10 7 22
-47 -23 -34 8
44 27 14 47
50 -13 -43 -48
44 -15 20 -12
-42 -34 11 -5
50 -5 -32 19
17 -39 46 -27
50 -2 11 20
-1 29 30 31

output:

0.000000000000000

result:

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

Test #18:

score: 0
Accepted
time: 4ms
memory: 5704kb

input:

100 10000 10
0 9993 -10000 9997
-8432 1663 -4444 1091
-6362 3959 -103 1099
-6051 -8548 -5705 -3821
-1799 4343 -9251 8281
-10000 -1137 -6247 718
-10000 -1352 -641 -1609
-2741 -1688 -2924 -3518
-10000 5035 -7198 5857
-4181 -9929 -3009 -6350
-9568 -9578 -7653 -9810
-9208 2799 -8703 3189
-10000 -3228 -3...

output:

0.001500525183814

result:

ok found '0.0015005', expected '0.0015005', error '0.0000000'

Test #19:

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

input:

7 70 6
-63 -598 7 -598
70 260 14 104
35 26 -21 -182
-21 -286 -21 -494
-56 -208 -56 -572
-70 0 0 0
-42 -208 -14 -208

output:

1.615384615384615

result:

ok found '1.6153846', expected '1.6153846', error '0.0000000'

Test #20:

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

input:

1 10 1
-10 0 -10 10

output:

0.000000000000000

result:

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

Test #21:

score: 0
Accepted
time: 2ms
memory: 5624kb

input:

2 3 1
2 0 2 3
-3 1 2 100

output:

0.000000000000000

result:

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

Test #22:

score: 0
Accepted
time: 2ms
memory: 5476kb

input:

3 3 1
-3 -3 2 -1
0 -1 0 2
-2 2 3 5

output:

-1

result:

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

Test #23:

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

input:

3 3 1
-3 -3 2 -1
0 0 0 2
-2 2 3 5

output:

2.000000000000000

result:

ok found '2.0000000', expected '2.0000000', error '0.0000000'

Test #24:

score: 0
Accepted
time: 2ms
memory: 5732kb

input:

5 3 1
-3 -3 0 0
0 -4 3 -4
0 1 0 2
0 -1 0 -2
0 -9 0 -1000

output:

0.000000000000000

result:

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