QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#168720 | #6426. Interested in Skiing | NOI_AK_ME | AC ✓ | 4ms | 5788kb | C++14 | 1.8kb | 2023-09-08 20:36:57 | 2023-09-08 20:36:58 |
Judging History
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'