QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#56583 | #2290. Kinking Cables | zghtyarecrenj | AC ✓ | 3ms | 3940kb | C++17 | 1.6kb | 2022-10-20 11:20:50 | 2022-10-20 11:20:51 |
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) {
if (i & 1) v.emplace_back(i, m), v.emplace_back(i, 0);
else 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: 2ms
memory: 3768kb
input:
79 78 1980.7712136406
output:
49 0.0000000000 0.0000000000 0.0000000000 78.0000000000 1.0000000000 78.0000000000 1.0000000000 0.0000000000 2.0000000000 0.0000000000 2.0000000000 78.0000000000 3.0000000000 78.0000000000 3.0000000000 0.0000000000 4.0000000000 0.0000000000 4.0000000000 78.0000000000 5.0000000000 78.0000000000 5.000...
result:
ok correct
Test #2:
score: 0
Accepted
time: 2ms
memory: 3788kb
input:
33 65 1947.7601065763
output:
61 0.0000000000 0.0000000000 0.0000000000 65.0000000000 1.0000000000 65.0000000000 1.0000000000 0.0000000000 2.0000000000 0.0000000000 2.0000000000 65.0000000000 3.0000000000 65.0000000000 3.0000000000 0.0000000000 4.0000000000 0.0000000000 4.0000000000 65.0000000000 5.0000000000 65.0000000000 5.000...
result:
ok correct
Test #3:
score: 0
Accepted
time: 2ms
memory: 3776kb
input:
51 51 555.0803652025
output:
21 0.0000000000 0.0000000000 0.0000000000 51.0000000000 1.0000000000 51.0000000000 1.0000000000 0.0000000000 2.0000000000 0.0000000000 2.0000000000 51.0000000000 3.0000000000 51.0000000000 3.0000000000 0.0000000000 4.0000000000 0.0000000000 4.0000000000 51.0000000000 5.0000000000 51.0000000000 5.000...
result:
ok correct
Test #4:
score: 0
Accepted
time: 1ms
memory: 3788kb
input:
49 2 67.3588717350
output:
21 0.0000000000 0.0000000000 0.0000000000 2.0000000000 1.0000000000 2.0000000000 1.0000000000 0.0000000000 2.0000000000 0.0000000000 2.0000000000 2.0000000000 3.0000000000 2.0000000000 3.0000000000 0.0000000000 4.0000000000 0.0000000000 4.0000000000 2.0000000000 5.0000000000 2.0000000000 5.000000000...
result:
ok correct
Test #5:
score: 0
Accepted
time: 2ms
memory: 3780kb
input:
37 48 1713.3643608504
output:
70 0.0000000000 0.0000000000 0.0000000000 48.0000000000 1.0000000000 48.0000000000 1.0000000000 0.0000000000 2.0000000000 0.0000000000 2.0000000000 48.0000000000 3.0000000000 48.0000000000 3.0000000000 0.0000000000 4.0000000000 0.0000000000 4.0000000000 48.0000000000 5.0000000000 48.0000000000 5.000...
result:
ok correct
Test #6:
score: 0
Accepted
time: 2ms
memory: 3784kb
input:
51 79 820.1218304546
output:
21 0.0000000000 0.0000000000 0.0000000000 79.0000000000 1.0000000000 79.0000000000 1.0000000000 0.0000000000 2.0000000000 0.0000000000 2.0000000000 79.0000000000 3.0000000000 79.0000000000 3.0000000000 0.0000000000 4.0000000000 0.0000000000 4.0000000000 79.0000000000 5.0000000000 79.0000000000 5.000...
result:
ok correct
Test #7:
score: 0
Accepted
time: 2ms
memory: 3788kb
input:
6 8 37.5338494218
output:
9 0.0000000000 0.0000000000 0.0000000000 8.0000000000 1.0000000000 8.0000000000 1.0000000000 0.0000000000 2.0000000000 0.0000000000 2.0000000000 8.0000000000 3.0000000000 8.0000000000 3.0000000000 3.1602695483 6 8
result:
ok correct
Test #8:
score: 0
Accepted
time: 0ms
memory: 3784kb
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: 3652kb
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: 3780kb
input:
4 2 6.4617533647
output:
5 0.0000000000 0.0000000000 0.0000000000 2.0000000000 1.0000000000 2.0000000000 1.0000000000 1.5690426146 4 2
result:
ok correct
Test #11:
score: 0
Accepted
time: 2ms
memory: 3792kb
input:
91 87 4830.8473359767
output:
109 0.0000000000 0.0000000000 0.0000000000 87.0000000000 1.0000000000 87.0000000000 1.0000000000 0.0000000000 2.0000000000 0.0000000000 2.0000000000 87.0000000000 3.0000000000 87.0000000000 3.0000000000 0.0000000000 4.0000000000 0.0000000000 4.0000000000 87.0000000000 5.0000000000 87.0000000000 5.00...
result:
ok correct
Test #12:
score: 0
Accepted
time: 2ms
memory: 3756kb
input:
90 90 5088.9280941138
output:
113 0.0000000000 0.0000000000 0.0000000000 90.0000000000 1.0000000000 90.0000000000 1.0000000000 0.0000000000 2.0000000000 0.0000000000 2.0000000000 90.0000000000 3.0000000000 90.0000000000 3.0000000000 0.0000000000 4.0000000000 0.0000000000 4.0000000000 90.0000000000 5.0000000000 90.0000000000 5.00...
result:
ok correct
Test #13:
score: 0
Accepted
time: 2ms
memory: 3776kb
input:
90 92 7004.0153432299
output:
153 0.0000000000 0.0000000000 0.0000000000 92.0000000000 1.0000000000 92.0000000000 1.0000000000 0.0000000000 2.0000000000 0.0000000000 2.0000000000 92.0000000000 3.0000000000 92.0000000000 3.0000000000 0.0000000000 4.0000000000 0.0000000000 4.0000000000 92.0000000000 5.0000000000 92.0000000000 5.00...
result:
ok correct
Test #14:
score: 0
Accepted
time: 2ms
memory: 3720kb
input:
91 83 1879.3819547895
output:
45 0.0000000000 0.0000000000 0.0000000000 83.0000000000 1.0000000000 83.0000000000 1.0000000000 0.0000000000 2.0000000000 0.0000000000 2.0000000000 83.0000000000 3.0000000000 83.0000000000 3.0000000000 0.0000000000 4.0000000000 0.0000000000 4.0000000000 83.0000000000 5.0000000000 83.0000000000 5.000...
result:
ok correct
Test #15:
score: 0
Accepted
time: 2ms
memory: 3784kb
input:
3 81 199.2077743610
output:
5 0.0000000000 0.0000000000 0.0000000000 81.0000000000 1.0000000000 81.0000000000 1.0000000000 22.4131765340 3 81
result:
ok correct
Test #16:
score: 0
Accepted
time: 1ms
memory: 3856kb
input:
4 89 288.5915130114
output:
9 0.0000000000 0.0000000000 0.0000000000 89.0000000000 1.0000000000 89.0000000000 1.0000000000 0.0000000000 2.0000000000 0.0000000000 2.0000000000 89.0000000000 3.0000000000 89.0000000000 3.0000000000 79.7311374862 4 89
result:
ok correct
Test #17:
score: 0
Accepted
time: 2ms
memory: 3660kb
input:
95 3 175.9210001082
output:
55 0.0000000000 0.0000000000 0.0000000000 3.0000000000 1.0000000000 3.0000000000 1.0000000000 0.0000000000 2.0000000000 0.0000000000 2.0000000000 3.0000000000 3.0000000000 3.0000000000 3.0000000000 0.0000000000 4.0000000000 0.0000000000 4.0000000000 3.0000000000 5.0000000000 3.0000000000 5.000000000...
result:
ok correct
Test #18:
score: 0
Accepted
time: 2ms
memory: 3776kb
input:
84 4 310.3037172015
output:
115 0.0000000000 0.0000000000 0.0000000000 4.0000000000 1.0000000000 4.0000000000 1.0000000000 0.0000000000 2.0000000000 0.0000000000 2.0000000000 4.0000000000 3.0000000000 4.0000000000 3.0000000000 0.0000000000 4.0000000000 0.0000000000 4.0000000000 4.0000000000 5.0000000000 4.0000000000 5.00000000...
result:
ok correct
Test #19:
score: 0
Accepted
time: 0ms
memory: 3816kb
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: 3792kb
input:
100 100 10000.0000000000
output:
200 0.0000000000 0.0000000000 0.0000000000 100.0000000000 1.0000000000 100.0000000000 1.0000000000 0.0000000000 2.0000000000 0.0000000000 2.0000000000 100.0000000000 3.0000000000 100.0000000000 3.0000000000 0.0000000000 4.0000000000 0.0000000000 4.0000000000 100.0000000000 5.0000000000 100.000000000...
result:
ok correct
Test #21:
score: 0
Accepted
time: 2ms
memory: 3940kb
input:
100 100 9999.2500000000
output:
199 0.0000000000 0.0000000000 0.0000000000 100.0000000000 1.0000000000 100.0000000000 1.0000000000 0.0000000000 2.0000000000 0.0000000000 2.0000000000 100.0000000000 3.0000000000 100.0000000000 3.0000000000 0.0000000000 4.0000000000 0.0000000000 4.0000000000 100.0000000000 5.0000000000 100.000000000...
result:
ok correct
Test #22:
score: 0
Accepted
time: 2ms
memory: 3664kb
input:
100 100 2723.8981892905
output:
53 0.0000000000 0.0000000000 0.0000000000 100.0000000000 1.0000000000 100.0000000000 1.0000000000 0.0000000000 2.0000000000 0.0000000000 2.0000000000 100.0000000000 3.0000000000 100.0000000000 3.0000000000 0.0000000000 4.0000000000 0.0000000000 4.0000000000 100.0000000000 5.0000000000 100.0000000000...
result:
ok correct
Test #23:
score: 0
Accepted
time: 1ms
memory: 3800kb
input:
100 100 8994.4904261819
output:
179 0.0000000000 0.0000000000 0.0000000000 100.0000000000 1.0000000000 100.0000000000 1.0000000000 0.0000000000 2.0000000000 0.0000000000 2.0000000000 100.0000000000 3.0000000000 100.0000000000 3.0000000000 0.0000000000 4.0000000000 0.0000000000 4.0000000000 100.0000000000 5.0000000000 100.000000000...
result:
ok correct
Test #24:
score: 0
Accepted
time: 2ms
memory: 3828kb
input:
100 100 881.4998747190
output:
17 0.0000000000 0.0000000000 0.0000000000 100.0000000000 1.0000000000 100.0000000000 1.0000000000 0.0000000000 2.0000000000 0.0000000000 2.0000000000 100.0000000000 3.0000000000 100.0000000000 3.0000000000 0.0000000000 4.0000000000 0.0000000000 4.0000000000 100.0000000000 5.0000000000 100.0000000000...
result:
ok correct
Test #25:
score: 0
Accepted
time: 2ms
memory: 3780kb
input:
88 94 8266.2500000000
output:
177 0.0000000000 0.0000000000 0.0000000000 94.0000000000 1.0000000000 94.0000000000 1.0000000000 0.0000000000 2.0000000000 0.0000000000 2.0000000000 94.0000000000 3.0000000000 94.0000000000 3.0000000000 0.0000000000 4.0000000000 0.0000000000 4.0000000000 94.0000000000 5.0000000000 94.0000000000 5.00...
result:
ok correct
Test #26:
score: 0
Accepted
time: 1ms
memory: 3800kb
input:
75 37 2772.0000000000
output:
145 0.0000000000 0.0000000000 0.0000000000 37.0000000000 1.0000000000 37.0000000000 1.0000000000 0.0000000000 2.0000000000 0.0000000000 2.0000000000 37.0000000000 3.0000000000 37.0000000000 3.0000000000 0.0000000000 4.0000000000 0.0000000000 4.0000000000 37.0000000000 5.0000000000 37.0000000000 5.00...
result:
ok correct
Test #27:
score: 0
Accepted
time: 1ms
memory: 3856kb
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: 3768kb
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: 3888kb
input:
90 81 7290.0000000000
output:
177 0.0000000000 0.0000000000 0.0000000000 81.0000000000 1.0000000000 81.0000000000 1.0000000000 0.0000000000 2.0000000000 0.0000000000 2.0000000000 81.0000000000 3.0000000000 81.0000000000 3.0000000000 0.0000000000 4.0000000000 0.0000000000 4.0000000000 81.0000000000 5.0000000000 81.0000000000 5.00...
result:
ok correct
Test #30:
score: 0
Accepted
time: 0ms
memory: 3888kb
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: 0ms
memory: 3776kb
input:
34 99 3366.0000000000
output:
69 0.0000000000 0.0000000000 0.0000000000 99.0000000000 1.0000000000 99.0000000000 1.0000000000 0.0000000000 2.0000000000 0.0000000000 2.0000000000 99.0000000000 3.0000000000 99.0000000000 3.0000000000 0.0000000000 4.0000000000 0.0000000000 4.0000000000 99.0000000000 5.0000000000 99.0000000000 5.000...
result:
ok correct
Test #32:
score: 0
Accepted
time: 3ms
memory: 3864kb
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: 3ms
memory: 3784kb
input:
3 3 6.0
output:
4 0.0000000000 0.0000000000 0.0000000000 3.0000000000 1.0000000000 3.0000000000 3 3
result:
ok correct
Test #35:
score: 0
Accepted
time: 0ms
memory: 3652kb
input:
3 3 6.0001
output:
5 0.0000000000 0.0000000000 0.0000000000 3.0000000000 1.0000000000 3.0000000000 1.0000000000 2.9999000025 3 3
result:
ok correct
Test #36:
score: 0
Accepted
time: 0ms
memory: 3768kb
input:
4 4 13.999998
output:
5 0.0000000000 0.0000000000 0.0000000000 4.0000000000 1.0000000000 4.0000000000 1.0000000000 0.0000011111 4 4
result:
ok correct
Test #37:
score: 0
Accepted
time: 2ms
memory: 3764kb
input:
4 4 14.0
output:
5 0.0000000000 0.0000000000 0.0000000000 4.0000000000 1.0000000000 4.0000000000 1.0000000000 0.0000000000 4 4
result:
ok correct
Test #38:
score: 0
Accepted
time: 2ms
memory: 3784kb
input:
4 4 14.000002
output:
6 0.0000000000 0.0000000000 0.0000000000 4.0000000000 1.0000000000 4.0000000000 1.0000000000 0.0000000000 1.0000050000 0.0000000000 4 4
result:
ok correct
Test #39:
score: 0
Accepted
time: 2ms
memory: 3784kb
input:
4 4 15.123104
output:
7 0.0000000000 0.0000000000 0.0000000000 4.0000000000 1.0000000000 4.0000000000 1.0000000000 0.0000000000 2.0000000000 0.0000000000 2.0000000000 2.7807730160 4 4
result:
ok correct
Test #40:
score: 0
Accepted
time: 2ms
memory: 3796kb
input:
4 4 15.123106
output:
7 0.0000000000 0.0000000000 0.0000000000 4.0000000000 1.0000000000 4.0000000000 1.0000000000 0.0000000000 2.0000000000 0.0000000000 2.0000000000 2.7807771872 4 4
result:
ok correct
Test #41:
score: 0
Accepted
time: 2ms
memory: 3928kb
input:
4 4 15.123108
output:
7 0.0000000000 0.0000000000 0.0000000000 4.0000000000 1.0000000000 4.0000000000 1.0000000000 0.0000000000 2.0000000000 0.0000000000 2.0000000000 2.7807813584 4 4
result:
ok correct
Test #42:
score: 0
Accepted
time: 2ms
memory: 3776kb
input:
4 4 14.593385
output:
7 0.0000000000 0.0000000000 0.0000000000 4.0000000000 1.0000000000 4.0000000000 1.0000000000 0.0000000000 2.0000000000 0.0000000000 2.0000000000 0.9261994811 4 4
result:
ok correct
Test #43:
score: 0
Accepted
time: 2ms
memory: 3720kb
input:
4 4 14.593387
output:
7 0.0000000000 0.0000000000 0.0000000000 4.0000000000 1.0000000000 4.0000000000 1.0000000000 0.0000000000 2.0000000000 0.0000000000 2.0000000000 0.9262118413 4 4
result:
ok correct
Test #44:
score: 0
Accepted
time: 2ms
memory: 3928kb
input:
4 4 14.593389
output:
7 0.0000000000 0.0000000000 0.0000000000 4.0000000000 1.0000000000 4.0000000000 1.0000000000 0.0000000000 2.0000000000 0.0000000000 2.0000000000 0.9262242014 4 4
result:
ok correct
Test #45:
score: 0
Accepted
time: 2ms
memory: 3792kb
input:
2 2 4.0
output:
4 0.0000000000 0.0000000000 0.0000000000 2.0000000000 1.0000000000 2.0000000000 2 2
result:
ok correct
Test #46:
score: 0
Accepted
time: 2ms
memory: 3756kb
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: 2ms
memory: 3748kb
input:
4 4 15.123
output:
7 0.0000000000 0.0000000000 0.0000000000 4.0000000000 1.0000000000 4.0000000000 1.0000000000 0.0000000000 2.0000000000 0.0000000000 2.0000000000 2.7805560997 4 4
result:
ok correct
Test #48:
score: 0
Accepted
time: 0ms
memory: 3764kb
input:
4 4 14.1
output:
6 0.0000000000 0.0000000000 0.0000000000 4.0000000000 1.0000000000 4.0000000000 1.0000000000 0.0000000000 1.2404761905 0.0000000000 4 4
result:
ok correct
Test #49:
score: 0
Accepted
time: 1ms
memory: 3772kb
input:
3 3 9.0
output:
5 0.0000000000 0.0000000000 0.0000000000 3.0000000000 1.0000000000 3.0000000000 1.0000000000 0.9000000000 3 3
result:
ok correct
Test #50:
score: 0
Accepted
time: 0ms
memory: 3644kb
input:
4 4 16.0
output:
8 0.0000000000 0.0000000000 0.0000000000 4.0000000000 1.0000000000 4.0000000000 1.0000000000 0.0000000000 2.0000000000 0.0000000000 2.0000000000 4.0000000000 3.0000000000 4.0000000000 4 4
result:
ok correct