QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#353677 | #6426. Interested in Skiing | PorNPtree | WA | 9ms | 3952kb | C++14 | 2.3kb | 2024-03-14 14:51:24 | 2024-03-14 14:51:25 |
Judging History
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() / 1e15, b += (double)rnd() / 1e15, c += (double)rnd() / 1e15, d += (double)rnd() / 1e15;
e += (double)rnd() / 1e15, f += (double)rnd() / 1e15, g += (double)rnd() / 1e15, h += (double)rnd() / 1e15;
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-4 && ix < max(a, c) + 1e-4 && ix > min(e, g) - 1e-4 && ix < max(e, g) + 1e-4 && iy > min(b, d) - 1e-4 && iy < max(b, d) + 1e-4 && iy > min(f, h) - 1e-4 && iy < max(f, h) + 1e-4 && fabs(ix - a) + fabs(iy - b) > 1e-4 && fabs(ix - c) + fabs(iy - d) > 1e-4 && fabs(ix - e) + fabs(iy - f) > 1e-4 && fabs(ix - g) + fabs(iy - h) > 1e-4;
}
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);
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: 3916kb
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: 1ms
memory: 3724kb
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: 3916kb
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: 3832kb
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: 3848kb
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: 1ms
memory: 3904kb
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: 0ms
memory: 3952kb
input:
2 1 2 -1 0 0 0 1 1 0 1
output:
0.0000000000
result:
ok found '0.0000000', expected '0.0000000', error '-0.0000000'
Test #8:
score: 0
Accepted
time: 0ms
memory: 3804kb
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: 3904kb
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: 1ms
memory: 3844kb
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: 3908kb
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: 3932kb
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: 3936kb
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: 5ms
memory: 3912kb
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:
921.6000000000
result:
wrong answer 1st numbers differ - expected: '3037.1538462', found: '921.6000000', error = '0.6965580'