QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#56582 | #2290. Kinking Cables | zghtyarecrenj | WA | 2ms | 3932kb | C++17 | 1.5kb | 2022-10-20 11:18:31 | 2022-10-20 11:18:33 |
Judging History
answer
#include <bits/stdc++.h>
typedef double db;
typedef long double ld;
const ld eps = 1e-12;
inline ld dist(ld x1, ld y1, ld x2, ld y2) {
return sqrt((x2 - x1) * (x2 - x1) + (y2 - y1) * (y2 - y1));
}
inline ld dist(std::pair<ld, ld> x, std::pair<ld, ld> y) {
return dist(x.first, x.second, y.first, y.second);
}
int n, m;
ld t;
std::vector<std::pair<ld, ld>> v;
int main() {
scanf("%d%d%Lf", &n, &m, &t);
std::pair<ld, ld> des(n, m), add(-1, -1);
for (int i = 0; i <= n; ++i)
v.emplace_back(i, 0), v.emplace_back(i, m);
int fin = 0;
for (int i = 1; i < v.size(); ++i) {
if (dist(v[i], v[i - 1]) + dist(v[i], des) > t + eps) {
fin = i;
ld l = 0, r = 1;
for (int j = 0; j < 256; ++j) {
ld mid = (l + r) / 2.0;
std::pair<ld, ld> cur(v[i - 1].first * (1 - mid) + v[i].first * mid, v[i - 1].second * (1 - mid) + v[i].second * mid);
if (dist(v[i - 1], cur) + dist(cur, des) > t) r = mid; else l = mid;
}
std::pair<ld, ld> cur(v[i - 1].first * (1 - l) + v[i].first * l, v[i - 1].second * (1 - l) + v[i].second * l);
if (dist(cur, v[i - 1]) > eps) add = cur;
break;
}
t -= dist(v[i], v[i - 1]);
}
printf("%d\n", fin + (add.first != -1) + 1);
for (int i = 0; i < fin; ++i) printf("%.10Lf %.10Lf\n", v[i].first, v[i].second);
if (add.first != -1) printf("%.10Lf %.10Lf\n", add.first, add.second);
printf("%d %d\n", n, m);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3788kb
input:
79 78 1980.7712136406
output:
27 0.0000000000 0.0000000000 0.0000000000 78.0000000000 1.0000000000 0.0000000000 1.0000000000 78.0000000000 2.0000000000 0.0000000000 2.0000000000 78.0000000000 3.0000000000 0.0000000000 3.0000000000 78.0000000000 4.0000000000 0.0000000000 4.0000000000 78.0000000000 5.0000000000 0.0000000000 5.0000...
result:
ok correct
Test #2:
score: 0
Accepted
time: 2ms
memory: 3764kb
input:
33 65 1947.7601065763
output:
32 0.0000000000 0.0000000000 0.0000000000 65.0000000000 1.0000000000 0.0000000000 1.0000000000 65.0000000000 2.0000000000 0.0000000000 2.0000000000 65.0000000000 3.0000000000 0.0000000000 3.0000000000 65.0000000000 4.0000000000 0.0000000000 4.0000000000 65.0000000000 5.0000000000 0.0000000000 5.0000...
result:
ok correct
Test #3:
score: 0
Accepted
time: 2ms
memory: 3876kb
input:
51 51 555.0803652025
output:
12 0.0000000000 0.0000000000 0.0000000000 51.0000000000 1.0000000000 0.0000000000 1.0000000000 51.0000000000 2.0000000000 0.0000000000 2.0000000000 51.0000000000 3.0000000000 0.0000000000 3.0000000000 51.0000000000 4.0000000000 0.0000000000 4.0000000000 51.0000000000 4.7228817859 14.1330289215 51 51
result:
ok correct
Test #4:
score: 0
Accepted
time: 2ms
memory: 3932kb
input:
49 2 67.3588717350
output:
14 0.0000000000 0.0000000000 0.0000000000 2.0000000000 1.0000000000 0.0000000000 1.0000000000 2.0000000000 2.0000000000 0.0000000000 2.0000000000 2.0000000000 3.0000000000 0.0000000000 3.0000000000 2.0000000000 4.0000000000 0.0000000000 4.0000000000 2.0000000000 5.0000000000 0.0000000000 5.000000000...
result:
ok correct
Test #5:
score: 0
Accepted
time: 2ms
memory: 3768kb
input:
37 48 1713.3643608504
output:
38 0.0000000000 0.0000000000 0.0000000000 48.0000000000 1.0000000000 0.0000000000 1.0000000000 48.0000000000 2.0000000000 0.0000000000 2.0000000000 48.0000000000 3.0000000000 0.0000000000 3.0000000000 48.0000000000 4.0000000000 0.0000000000 4.0000000000 48.0000000000 5.0000000000 0.0000000000 5.0000...
result:
ok correct
Test #6:
score: 0
Accepted
time: 2ms
memory: 3884kb
input:
51 79 820.1218304546
output:
12 0.0000000000 0.0000000000 0.0000000000 79.0000000000 1.0000000000 0.0000000000 1.0000000000 79.0000000000 2.0000000000 0.0000000000 2.0000000000 79.0000000000 3.0000000000 0.0000000000 3.0000000000 79.0000000000 4.0000000000 0.0000000000 4.0000000000 79.0000000000 4.5653694146 34.3358162464 51 79
result:
ok correct
Test #7:
score: 0
Accepted
time: 2ms
memory: 3796kb
input:
6 8 37.5338494218
output:
6 0.0000000000 0.0000000000 0.0000000000 8.0000000000 1.0000000000 0.0000000000 1.0000000000 8.0000000000 1.7551471905 1.9588224758 6 8
result:
ok correct
Test #8:
score: 0
Accepted
time: 2ms
memory: 3712kb
input:
5 5 7.1908428511
output:
3 0.0000000000 0.0000000000 0.0000000000 0.3898547329 5 5
result:
ok correct
Test #9:
score: 0
Accepted
time: 2ms
memory: 3828kb
input:
5 4 8.3927665498
output:
3 0.0000000000 0.0000000000 0.0000000000 3.3507961356 5 4
result:
ok correct
Test #10:
score: 0
Accepted
time: 2ms
memory: 3884kb
input:
4 2 6.4617533647
output:
4 0.0000000000 0.0000000000 0.0000000000 2.0000000000 0.3268683630 1.3462632741 4 2
result:
ok correct
Test #11:
score: 0
Accepted
time: 2ms
memory: 3772kb
input:
91 87 4830.8473359767
output:
57 0.0000000000 0.0000000000 0.0000000000 87.0000000000 1.0000000000 0.0000000000 1.0000000000 87.0000000000 2.0000000000 0.0000000000 2.0000000000 87.0000000000 3.0000000000 0.0000000000 3.0000000000 87.0000000000 4.0000000000 0.0000000000 4.0000000000 87.0000000000 5.0000000000 0.0000000000 5.0000...
result:
ok correct
Test #12:
score: 0
Accepted
time: 0ms
memory: 3820kb
input:
90 90 5088.9280941138
output:
58 0.0000000000 0.0000000000 0.0000000000 90.0000000000 1.0000000000 0.0000000000 1.0000000000 90.0000000000 2.0000000000 0.0000000000 2.0000000000 90.0000000000 3.0000000000 0.0000000000 3.0000000000 90.0000000000 4.0000000000 0.0000000000 4.0000000000 90.0000000000 5.0000000000 0.0000000000 5.0000...
result:
ok correct
Test #13:
score: 0
Accepted
time: 2ms
memory: 3796kb
input:
90 92 7004.0153432299
output:
78 0.0000000000 0.0000000000 0.0000000000 92.0000000000 1.0000000000 0.0000000000 1.0000000000 92.0000000000 2.0000000000 0.0000000000 2.0000000000 92.0000000000 3.0000000000 0.0000000000 3.0000000000 92.0000000000 4.0000000000 0.0000000000 4.0000000000 92.0000000000 5.0000000000 0.0000000000 5.0000...
result:
ok correct
Test #14:
score: 0
Accepted
time: 2ms
memory: 3656kb
input:
91 83 1879.3819547895
output:
24 0.0000000000 0.0000000000 0.0000000000 83.0000000000 1.0000000000 0.0000000000 1.0000000000 83.0000000000 2.0000000000 0.0000000000 2.0000000000 83.0000000000 3.0000000000 0.0000000000 3.0000000000 83.0000000000 4.0000000000 0.0000000000 4.0000000000 83.0000000000 5.0000000000 0.0000000000 5.0000...
result:
ok correct
Test #15:
score: 0
Accepted
time: 2ms
memory: 3784kb
input:
3 81 199.2077743610
output:
4 0.0000000000 0.0000000000 0.0000000000 81.0000000000 0.7293805854 21.9201725793 3 81
result:
ok correct
Test #16:
score: 0
Accepted
time: 2ms
memory: 3772kb
input:
4 89 288.5915130114
output:
6 0.0000000000 0.0000000000 0.0000000000 89.0000000000 1.0000000000 0.0000000000 1.0000000000 89.0000000000 1.1191051936 78.3996377702 4 89
result:
ok correct
Test #17:
score: 0
Accepted
time: 2ms
memory: 3792kb
input:
95 3 175.9210001082
output:
34 0.0000000000 0.0000000000 0.0000000000 3.0000000000 1.0000000000 0.0000000000 1.0000000000 3.0000000000 2.0000000000 0.0000000000 2.0000000000 3.0000000000 3.0000000000 0.0000000000 3.0000000000 3.0000000000 4.0000000000 0.0000000000 4.0000000000 3.0000000000 5.0000000000 0.0000000000 5.000000000...
result:
ok correct
Test #18:
score: 0
Accepted
time: 2ms
memory: 3784kb
input:
84 4 310.3037172015
output:
66 0.0000000000 0.0000000000 0.0000000000 4.0000000000 1.0000000000 0.0000000000 1.0000000000 4.0000000000 2.0000000000 0.0000000000 2.0000000000 4.0000000000 3.0000000000 0.0000000000 3.0000000000 4.0000000000 4.0000000000 0.0000000000 4.0000000000 4.0000000000 5.0000000000 0.0000000000 5.000000000...
result:
ok correct
Test #19:
score: 0
Accepted
time: 2ms
memory: 3776kb
input:
2 2 2.8284271248
output:
3 0.0000000000 0.0000000000 0.0000000000 0.0000000002 2 2
result:
ok correct
Test #20:
score: 0
Accepted
time: 2ms
memory: 3932kb
input:
100 100 10000.0000000000
output:
102 0.0000000000 0.0000000000 0.0000000000 100.0000000000 1.0000000000 0.0000000000 1.0000000000 100.0000000000 2.0000000000 0.0000000000 2.0000000000 100.0000000000 3.0000000000 0.0000000000 3.0000000000 100.0000000000 4.0000000000 0.0000000000 4.0000000000 100.0000000000 5.0000000000 0.0000000000 ...
result:
ok correct
Test #21:
score: 0
Accepted
time: 2ms
memory: 3752kb
input:
100 100 9999.2500000000
output:
102 0.0000000000 0.0000000000 0.0000000000 100.0000000000 1.0000000000 0.0000000000 1.0000000000 100.0000000000 2.0000000000 0.0000000000 2.0000000000 100.0000000000 3.0000000000 0.0000000000 3.0000000000 100.0000000000 4.0000000000 0.0000000000 4.0000000000 100.0000000000 5.0000000000 0.0000000000 ...
result:
ok correct
Test #22:
score: 0
Accepted
time: 0ms
memory: 3776kb
input:
100 100 2723.8981892905
output:
28 0.0000000000 0.0000000000 0.0000000000 100.0000000000 1.0000000000 0.0000000000 1.0000000000 100.0000000000 2.0000000000 0.0000000000 2.0000000000 100.0000000000 3.0000000000 0.0000000000 3.0000000000 100.0000000000 4.0000000000 0.0000000000 4.0000000000 100.0000000000 5.0000000000 0.0000000000 5...
result:
ok correct
Test #23:
score: 0
Accepted
time: 2ms
memory: 3776kb
input:
100 100 8994.4904261819
output:
92 0.0000000000 0.0000000000 0.0000000000 100.0000000000 1.0000000000 0.0000000000 1.0000000000 100.0000000000 2.0000000000 0.0000000000 2.0000000000 100.0000000000 3.0000000000 0.0000000000 3.0000000000 100.0000000000 4.0000000000 0.0000000000 4.0000000000 100.0000000000 5.0000000000 0.0000000000 5...
result:
ok correct
Test #24:
score: 0
Accepted
time: 2ms
memory: 3788kb
input:
100 100 881.4998747190
output:
10 0.0000000000 0.0000000000 0.0000000000 100.0000000000 1.0000000000 0.0000000000 1.0000000000 100.0000000000 2.0000000000 0.0000000000 2.0000000000 100.0000000000 3.0000000000 0.0000000000 3.0000000000 100.0000000000 3.6516520385 34.8347961482 100 100
result:
ok correct
Test #25:
score: 0
Accepted
time: 2ms
memory: 3828kb
input:
88 94 8266.2500000000
output:
90 0.0000000000 0.0000000000 0.0000000000 94.0000000000 1.0000000000 0.0000000000 1.0000000000 94.0000000000 2.0000000000 0.0000000000 2.0000000000 94.0000000000 3.0000000000 0.0000000000 3.0000000000 94.0000000000 4.0000000000 0.0000000000 4.0000000000 94.0000000000 5.0000000000 0.0000000000 5.0000...
result:
ok correct
Test #26:
score: 0
Accepted
time: 0ms
memory: 3908kb
input:
75 37 2772.0000000000
output:
76 0.0000000000 0.0000000000 0.0000000000 37.0000000000 1.0000000000 0.0000000000 1.0000000000 37.0000000000 2.0000000000 0.0000000000 2.0000000000 37.0000000000 3.0000000000 0.0000000000 3.0000000000 37.0000000000 4.0000000000 0.0000000000 4.0000000000 37.0000000000 5.0000000000 0.0000000000 5.0000...
result:
ok correct
Test #27:
score: 0
Accepted
time: 0ms
memory: 3776kb
input:
48 39 62.0000000000
output:
3 0.0000000000 0.0000000000 0.0000000000 0.4130434783 48 39
result:
ok correct
Test #28:
score: 0
Accepted
time: 2ms
memory: 3776kb
input:
98 94 135.9000000000
output:
3 0.0000000000 0.0000000000 0.0000000000 0.3437947494 98 94
result:
ok correct
Test #29:
score: 0
Accepted
time: 2ms
memory: 3768kb
input:
90 81 7290.0000000000
output:
92 0.0000000000 0.0000000000 0.0000000000 81.0000000000 1.0000000000 0.0000000000 1.0000000000 81.0000000000 2.0000000000 0.0000000000 2.0000000000 81.0000000000 3.0000000000 0.0000000000 3.0000000000 81.0000000000 4.0000000000 0.0000000000 4.0000000000 81.0000000000 5.0000000000 0.0000000000 5.0000...
result:
ok correct
Test #30:
score: 0
Accepted
time: 2ms
memory: 3788kb
input:
90 81 121.0826164250
output:
3 0.0000000000 0.0000000000 0.0000000000 0.0000000040 90 81
result:
ok correct
Test #31:
score: 0
Accepted
time: 2ms
memory: 3652kb
input:
34 99 3366.0000000000
output:
36 0.0000000000 0.0000000000 0.0000000000 99.0000000000 1.0000000000 0.0000000000 1.0000000000 99.0000000000 2.0000000000 0.0000000000 2.0000000000 99.0000000000 3.0000000000 0.0000000000 3.0000000000 99.0000000000 4.0000000000 0.0000000000 4.0000000000 99.0000000000 5.0000000000 0.0000000000 5.0000...
result:
ok correct
Test #32:
score: 0
Accepted
time: 2ms
memory: 3776kb
input:
34 99 104.6756896330
output:
3 0.0000000000 0.0000000000 0.0000000000 0.0000000127 34 99
result:
ok correct
Test #33:
score: 0
Accepted
time: 2ms
memory: 3780kb
input:
3 3 5.9999
output:
3 0.0000000000 0.0000000000 0.0000000000 2.9998999983 3 3
result:
ok correct
Test #34:
score: 0
Accepted
time: 2ms
memory: 3768kb
input:
3 3 6.0
output:
3 0.0000000000 0.0000000000 0.0000000000 3.0000000000 3 3
result:
ok correct
Test #35:
score: 0
Accepted
time: 0ms
memory: 3764kb
input:
3 3 6.0001
output:
4 0.0000000000 0.0000000000 0.0000000000 3.0000000000 0.0000462460 2.9998612619 3 3
result:
ok correct
Test #36:
score: 0
Accepted
time: 2ms
memory: 3780kb
input:
4 4 13.999998
output:
5 0.0000000000 0.0000000000 0.0000000000 4.0000000000 1.0000000000 0.0000000000 1.0000000000 2.5408659842 4 4
result:
ok correct
Test #37:
score: 0
Accepted
time: 1ms
memory: 3748kb
input:
4 4 14.0
output:
5 0.0000000000 0.0000000000 0.0000000000 4.0000000000 1.0000000000 0.0000000000 1.0000000000 2.5408695390 4 4
result:
ok correct
Test #38:
score: 0
Accepted
time: 2ms
memory: 3780kb
input:
4 4 14.000002
output:
5 0.0000000000 0.0000000000 0.0000000000 4.0000000000 1.0000000000 0.0000000000 1.0000000000 2.5408730939 4 4
result:
ok correct
Test #39:
score: 0
Accepted
time: 0ms
memory: 3768kb
input:
4 4 15.123104
output:
5 0.0000000000 0.0000000000 0.0000000000 4.0000000000 1.0000000000 0.0000000000 1.0000000000 3.9999983744 4 4
result:
ok correct
Test #40:
score: 0
Accepted
time: 2ms
memory: 3772kb
input:
4 4 15.123106
output:
6 0.0000000000 0.0000000000 0.0000000000 4.0000000000 1.0000000000 0.0000000000 1.0000000000 4.0000000000 1.0000001199 3.9999995205 4 4
result:
ok correct
Test #41:
score: 0
Accepted
time: 2ms
memory: 3856kb
input:
4 4 15.123108
output:
6 0.0000000000 0.0000000000 0.0000000000 4.0000000000 1.0000000000 0.0000000000 1.0000000000 4.0000000000 1.0000007603 3.9999969589 4 4
result:
ok correct
Test #42:
score: 0
Accepted
time: 2ms
memory: 3928kb
input:
4 4 14.593385
output:
5 0.0000000000 0.0000000000 0.0000000000 4.0000000000 1.0000000000 0.0000000000 1.0000000000 3.4134833812 4 4
result:
ok correct
Test #43:
score: 0
Accepted
time: 2ms
memory: 3768kb
input:
4 4 14.593387
output:
5 0.0000000000 0.0000000000 0.0000000000 4.0000000000 1.0000000000 0.0000000000 1.0000000000 3.4134858560 4 4
result:
ok correct
Test #44:
score: 0
Accepted
time: 2ms
memory: 3820kb
input:
4 4 14.593389
output:
5 0.0000000000 0.0000000000 0.0000000000 4.0000000000 1.0000000000 0.0000000000 1.0000000000 3.4134883309 4 4
result:
ok correct
Test #45:
score: 0
Accepted
time: 2ms
memory: 3756kb
input:
2 2 4.0
output:
3 0.0000000000 0.0000000000 0.0000000000 2.0000000000 2 2
result:
ok correct
Test #46:
score: 0
Accepted
time: 2ms
memory: 3644kb
input:
3 3 5.0
output:
3 0.0000000000 0.0000000000 0.0000000000 1.7500000000 3 3
result:
ok correct
Test #47:
score: 0
Accepted
time: 0ms
memory: 3824kb
input:
4 4 15.123
output:
5 0.0000000000 0.0000000000 0.0000000000 4.0000000000 1.0000000000 0.0000000000 1.0000000000 3.9998943725 4 4
result:
ok correct
Test #48:
score: 0
Accepted
time: 0ms
memory: 3708kb
input:
4 4 14.1
output:
5 0.0000000000 0.0000000000 0.0000000000 4.0000000000 1.0000000000 0.0000000000 1.0000000000 2.7121495467 4 4
result:
ok correct
Test #49:
score: -100
Wrong Answer
time: 2ms
memory: 3768kb
input:
3 3 9.0
output:
4 0.0000000000 0.0000000000 0.0000000000 3.0000000000 0.8451409985 0.4645770045 3 3
result:
wrong answer Output path has non-consecutive points within distance 1 of each other: (0.000000000000,0.000000000000) and (0.845140998500,0.464577004500)lie too close to each other