QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#202447 | #2290. Kinking Cables | MaGnsi0 | AC ✓ | 1ms | 4064kb | C++17 | 1.9kb | 2023-10-06 03:11:07 | 2023-10-06 03:11:08 |
Judging History
answer
/**
* author: MaGnsi0
* created: 05.10.2023 21:43:55
**/
#include <bits/stdc++.h>
using namespace std;
const long double eps = 1e-6;
long double dist(long double x1, long double y1, long double x2, long double y2) {
long double dx = x1 - x2;
long double dy = y1 - y2;
return sqrt(dx * dx + dy * dy);
}
int main() {
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int n; cin >> n;
int m; cin >> m;
long double L; cin >> L;
int x = 0, y = 0;
vector<double> X(1, 0), Y(1, 0);
while (true) {
int x_ = x, y_ = y;
if (x % 2 == 0 && y == 0) { y_ = m; }
if (x % 2 == 0 && y == m) { x_++; }
if (x % 2 == 1 && y == 0) { x_++; }
if (x % 2 == 1 && y == m) { y_ = 0; }
long double D = dist(x, y, x_, y_) + dist(x_, y_, n, m);
if (L > D) {
L -= dist(x, y, x_, y_);
x = x_, y = y_;
X.push_back(x);
Y.push_back(y);
continue;
}
long double low = 0, high = 1;
for (int _ = 0; _ <= 100; _++) {
long double mid = (low + high) / 2;
long double x_mid = x_ * mid + x * (1 - mid);
long double y_mid = y_ * mid + y * (1 - mid);
D = dist(x, y, x_mid, y_mid) + dist(x_mid, y_mid, n, m);
if (L > D) {
low = mid;
} else {
high = mid;
}
}
long double x_mid = x_ * low + x * (1 - low);
long double y_mid = y_ * low + y * (1 - low);
if (low > 0 && low < 1) {
X.push_back(x_mid);
Y.push_back(y_mid);
}
X.push_back(n);
Y.push_back(m);
break;
}
int k = (int)X.size();
cout << k << "\n";
cout << fixed << setprecision(6);
for (int i = 0; i < k; ++i) {
cout << X[i] << " " << Y[i] << "\n";
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3816kb
input:
79 78 1980.7712136406
output:
49 0.000000 0.000000 0.000000 78.000000 1.000000 78.000000 1.000000 0.000000 2.000000 0.000000 2.000000 78.000000 3.000000 78.000000 3.000000 0.000000 4.000000 0.000000 4.000000 78.000000 5.000000 78.000000 5.000000 0.000000 6.000000 0.000000 6.000000 78.000000 7.000000 78.000000 7.000000 0.000000 8...
result:
ok correct
Test #2:
score: 0
Accepted
time: 0ms
memory: 4060kb
input:
33 65 1947.7601065763
output:
61 0.000000 0.000000 0.000000 65.000000 1.000000 65.000000 1.000000 0.000000 2.000000 0.000000 2.000000 65.000000 3.000000 65.000000 3.000000 0.000000 4.000000 0.000000 4.000000 65.000000 5.000000 65.000000 5.000000 0.000000 6.000000 0.000000 6.000000 65.000000 7.000000 65.000000 7.000000 0.000000 8...
result:
ok correct
Test #3:
score: 0
Accepted
time: 0ms
memory: 3816kb
input:
51 51 555.0803652025
output:
21 0.000000 0.000000 0.000000 51.000000 1.000000 51.000000 1.000000 0.000000 2.000000 0.000000 2.000000 51.000000 3.000000 51.000000 3.000000 0.000000 4.000000 0.000000 4.000000 51.000000 5.000000 51.000000 5.000000 0.000000 6.000000 0.000000 6.000000 51.000000 7.000000 51.000000 7.000000 0.000000 8...
result:
ok correct
Test #4:
score: 0
Accepted
time: 0ms
memory: 3880kb
input:
49 2 67.3588717350
output:
21 0.000000 0.000000 0.000000 2.000000 1.000000 2.000000 1.000000 0.000000 2.000000 0.000000 2.000000 2.000000 3.000000 2.000000 3.000000 0.000000 4.000000 0.000000 4.000000 2.000000 5.000000 2.000000 5.000000 0.000000 6.000000 0.000000 6.000000 2.000000 7.000000 2.000000 7.000000 0.000000 8.000000 ...
result:
ok correct
Test #5:
score: 0
Accepted
time: 0ms
memory: 3888kb
input:
37 48 1713.3643608504
output:
70 0.000000 0.000000 0.000000 48.000000 1.000000 48.000000 1.000000 0.000000 2.000000 0.000000 2.000000 48.000000 3.000000 48.000000 3.000000 0.000000 4.000000 0.000000 4.000000 48.000000 5.000000 48.000000 5.000000 0.000000 6.000000 0.000000 6.000000 48.000000 7.000000 48.000000 7.000000 0.000000 8...
result:
ok correct
Test #6:
score: 0
Accepted
time: 0ms
memory: 3884kb
input:
51 79 820.1218304546
output:
21 0.000000 0.000000 0.000000 79.000000 1.000000 79.000000 1.000000 0.000000 2.000000 0.000000 2.000000 79.000000 3.000000 79.000000 3.000000 0.000000 4.000000 0.000000 4.000000 79.000000 5.000000 79.000000 5.000000 0.000000 6.000000 0.000000 6.000000 79.000000 7.000000 79.000000 7.000000 0.000000 8...
result:
ok correct
Test #7:
score: 0
Accepted
time: 0ms
memory: 3884kb
input:
6 8 37.5338494218
output:
9 0.000000 0.000000 0.000000 8.000000 1.000000 8.000000 1.000000 0.000000 2.000000 0.000000 2.000000 8.000000 3.000000 8.000000 3.000000 3.160270 6.000000 8.000000
result:
ok correct
Test #8:
score: 0
Accepted
time: 0ms
memory: 3812kb
input:
5 5 7.1908428511
output:
3 0.000000 0.000000 0.000000 0.389855 5.000000 5.000000
result:
ok correct
Test #9:
score: 0
Accepted
time: 0ms
memory: 4060kb
input:
5 4 8.3927665498
output:
3 0.000000 0.000000 0.000000 3.350796 5.000000 4.000000
result:
ok correct
Test #10:
score: 0
Accepted
time: 0ms
memory: 3876kb
input:
4 2 6.4617533647
output:
5 0.000000 0.000000 0.000000 2.000000 1.000000 2.000000 1.000000 1.569043 4.000000 2.000000
result:
ok correct
Test #11:
score: 0
Accepted
time: 0ms
memory: 3908kb
input:
91 87 4830.8473359767
output:
109 0.000000 0.000000 0.000000 87.000000 1.000000 87.000000 1.000000 0.000000 2.000000 0.000000 2.000000 87.000000 3.000000 87.000000 3.000000 0.000000 4.000000 0.000000 4.000000 87.000000 5.000000 87.000000 5.000000 0.000000 6.000000 0.000000 6.000000 87.000000 7.000000 87.000000 7.000000 0.000000 ...
result:
ok correct
Test #12:
score: 0
Accepted
time: 0ms
memory: 3920kb
input:
90 90 5088.9280941138
output:
113 0.000000 0.000000 0.000000 90.000000 1.000000 90.000000 1.000000 0.000000 2.000000 0.000000 2.000000 90.000000 3.000000 90.000000 3.000000 0.000000 4.000000 0.000000 4.000000 90.000000 5.000000 90.000000 5.000000 0.000000 6.000000 0.000000 6.000000 90.000000 7.000000 90.000000 7.000000 0.000000 ...
result:
ok correct
Test #13:
score: 0
Accepted
time: 0ms
memory: 3892kb
input:
90 92 7004.0153432299
output:
153 0.000000 0.000000 0.000000 92.000000 1.000000 92.000000 1.000000 0.000000 2.000000 0.000000 2.000000 92.000000 3.000000 92.000000 3.000000 0.000000 4.000000 0.000000 4.000000 92.000000 5.000000 92.000000 5.000000 0.000000 6.000000 0.000000 6.000000 92.000000 7.000000 92.000000 7.000000 0.000000 ...
result:
ok correct
Test #14:
score: 0
Accepted
time: 0ms
memory: 3820kb
input:
91 83 1879.3819547895
output:
45 0.000000 0.000000 0.000000 83.000000 1.000000 83.000000 1.000000 0.000000 2.000000 0.000000 2.000000 83.000000 3.000000 83.000000 3.000000 0.000000 4.000000 0.000000 4.000000 83.000000 5.000000 83.000000 5.000000 0.000000 6.000000 0.000000 6.000000 83.000000 7.000000 83.000000 7.000000 0.000000 8...
result:
ok correct
Test #15:
score: 0
Accepted
time: 0ms
memory: 4040kb
input:
3 81 199.2077743610
output:
5 0.000000 0.000000 0.000000 81.000000 1.000000 81.000000 1.000000 22.413177 3.000000 81.000000
result:
ok correct
Test #16:
score: 0
Accepted
time: 0ms
memory: 3976kb
input:
4 89 288.5915130114
output:
9 0.000000 0.000000 0.000000 89.000000 1.000000 89.000000 1.000000 0.000000 2.000000 0.000000 2.000000 89.000000 3.000000 89.000000 3.000000 79.731137 4.000000 89.000000
result:
ok correct
Test #17:
score: 0
Accepted
time: 0ms
memory: 3900kb
input:
95 3 175.9210001082
output:
55 0.000000 0.000000 0.000000 3.000000 1.000000 3.000000 1.000000 0.000000 2.000000 0.000000 2.000000 3.000000 3.000000 3.000000 3.000000 0.000000 4.000000 0.000000 4.000000 3.000000 5.000000 3.000000 5.000000 0.000000 6.000000 0.000000 6.000000 3.000000 7.000000 3.000000 7.000000 0.000000 8.000000 ...
result:
ok correct
Test #18:
score: 0
Accepted
time: 0ms
memory: 3768kb
input:
84 4 310.3037172015
output:
115 0.000000 0.000000 0.000000 4.000000 1.000000 4.000000 1.000000 0.000000 2.000000 0.000000 2.000000 4.000000 3.000000 4.000000 3.000000 0.000000 4.000000 0.000000 4.000000 4.000000 5.000000 4.000000 5.000000 0.000000 6.000000 0.000000 6.000000 4.000000 7.000000 4.000000 7.000000 0.000000 8.000000...
result:
ok correct
Test #19:
score: 0
Accepted
time: 0ms
memory: 3756kb
input:
2 2 2.8284271248
output:
3 0.000000 0.000000 0.000000 0.000000 2.000000 2.000000
result:
ok correct
Test #20:
score: 0
Accepted
time: 1ms
memory: 3896kb
input:
100 100 10000.0000000000
output:
199 0.000000 0.000000 0.000000 100.000000 1.000000 100.000000 1.000000 0.000000 2.000000 0.000000 2.000000 100.000000 3.000000 100.000000 3.000000 0.000000 4.000000 0.000000 4.000000 100.000000 5.000000 100.000000 5.000000 0.000000 6.000000 0.000000 6.000000 100.000000 7.000000 100.000000 7.000000 0...
result:
ok correct
Test #21:
score: 0
Accepted
time: 1ms
memory: 3964kb
input:
100 100 9999.2500000000
output:
199 0.000000 0.000000 0.000000 100.000000 1.000000 100.000000 1.000000 0.000000 2.000000 0.000000 2.000000 100.000000 3.000000 100.000000 3.000000 0.000000 4.000000 0.000000 4.000000 100.000000 5.000000 100.000000 5.000000 0.000000 6.000000 0.000000 6.000000 100.000000 7.000000 100.000000 7.000000 0...
result:
ok correct
Test #22:
score: 0
Accepted
time: 0ms
memory: 3984kb
input:
100 100 2723.8981892905
output:
53 0.000000 0.000000 0.000000 100.000000 1.000000 100.000000 1.000000 0.000000 2.000000 0.000000 2.000000 100.000000 3.000000 100.000000 3.000000 0.000000 4.000000 0.000000 4.000000 100.000000 5.000000 100.000000 5.000000 0.000000 6.000000 0.000000 6.000000 100.000000 7.000000 100.000000 7.000000 0....
result:
ok correct
Test #23:
score: 0
Accepted
time: 0ms
memory: 4064kb
input:
100 100 8994.4904261819
output:
179 0.000000 0.000000 0.000000 100.000000 1.000000 100.000000 1.000000 0.000000 2.000000 0.000000 2.000000 100.000000 3.000000 100.000000 3.000000 0.000000 4.000000 0.000000 4.000000 100.000000 5.000000 100.000000 5.000000 0.000000 6.000000 0.000000 6.000000 100.000000 7.000000 100.000000 7.000000 0...
result:
ok correct
Test #24:
score: 0
Accepted
time: 0ms
memory: 4040kb
input:
100 100 881.4998747190
output:
17 0.000000 0.000000 0.000000 100.000000 1.000000 100.000000 1.000000 0.000000 2.000000 0.000000 2.000000 100.000000 3.000000 100.000000 3.000000 0.000000 4.000000 0.000000 4.000000 100.000000 5.000000 100.000000 5.000000 0.000000 6.000000 0.000000 6.000000 100.000000 7.000000 100.000000 7.000000 37...
result:
ok correct
Test #25:
score: 0
Accepted
time: 1ms
memory: 3928kb
input:
88 94 8266.2500000000
output:
177 0.000000 0.000000 0.000000 94.000000 1.000000 94.000000 1.000000 0.000000 2.000000 0.000000 2.000000 94.000000 3.000000 94.000000 3.000000 0.000000 4.000000 0.000000 4.000000 94.000000 5.000000 94.000000 5.000000 0.000000 6.000000 0.000000 6.000000 94.000000 7.000000 94.000000 7.000000 0.000000 ...
result:
ok correct
Test #26:
score: 0
Accepted
time: 0ms
memory: 3924kb
input:
75 37 2772.0000000000
output:
145 0.000000 0.000000 0.000000 37.000000 1.000000 37.000000 1.000000 0.000000 2.000000 0.000000 2.000000 37.000000 3.000000 37.000000 3.000000 0.000000 4.000000 0.000000 4.000000 37.000000 5.000000 37.000000 5.000000 0.000000 6.000000 0.000000 6.000000 37.000000 7.000000 37.000000 7.000000 0.000000 ...
result:
ok correct
Test #27:
score: 0
Accepted
time: 0ms
memory: 3824kb
input:
48 39 62.0000000000
output:
3 0.000000 0.000000 0.000000 0.413043 48.000000 39.000000
result:
ok correct
Test #28:
score: 0
Accepted
time: 0ms
memory: 3880kb
input:
98 94 135.9000000000
output:
3 0.000000 0.000000 0.000000 0.343795 98.000000 94.000000
result:
ok correct
Test #29:
score: 0
Accepted
time: 1ms
memory: 3896kb
input:
90 81 7290.0000000000
output:
177 0.000000 0.000000 0.000000 81.000000 1.000000 81.000000 1.000000 0.000000 2.000000 0.000000 2.000000 81.000000 3.000000 81.000000 3.000000 0.000000 4.000000 0.000000 4.000000 81.000000 5.000000 81.000000 5.000000 0.000000 6.000000 0.000000 6.000000 81.000000 7.000000 81.000000 7.000000 0.000000 ...
result:
ok correct
Test #30:
score: 0
Accepted
time: 0ms
memory: 3876kb
input:
90 81 121.0826164250
output:
3 0.000000 0.000000 0.000000 0.000000 90.000000 81.000000
result:
ok correct
Test #31:
score: 0
Accepted
time: 0ms
memory: 4064kb
input:
34 99 3366.0000000000
output:
69 0.000000 0.000000 0.000000 99.000000 1.000000 99.000000 1.000000 0.000000 2.000000 0.000000 2.000000 99.000000 3.000000 99.000000 3.000000 0.000000 4.000000 0.000000 4.000000 99.000000 5.000000 99.000000 5.000000 0.000000 6.000000 0.000000 6.000000 99.000000 7.000000 99.000000 7.000000 0.000000 8...
result:
ok correct
Test #32:
score: 0
Accepted
time: 0ms
memory: 4040kb
input:
34 99 104.6756896330
output:
3 0.000000 0.000000 0.000000 0.000000 34.000000 99.000000
result:
ok correct
Test #33:
score: 0
Accepted
time: 0ms
memory: 3884kb
input:
3 3 5.9999
output:
3 0.000000 0.000000 0.000000 2.999900 3.000000 3.000000
result:
ok correct
Test #34:
score: 0
Accepted
time: 0ms
memory: 3884kb
input:
3 3 6.0
output:
3 0.000000 0.000000 0.000000 3.000000 3.000000 3.000000
result:
ok correct
Test #35:
score: 0
Accepted
time: 0ms
memory: 3836kb
input:
3 3 6.0001
output:
5 0.000000 0.000000 0.000000 3.000000 1.000000 3.000000 1.000000 2.999900 3.000000 3.000000
result:
ok correct
Test #36:
score: 0
Accepted
time: 0ms
memory: 3764kb
input:
4 4 13.999998
output:
5 0.000000 0.000000 0.000000 4.000000 1.000000 4.000000 1.000000 0.000001 4.000000 4.000000
result:
ok correct
Test #37:
score: 0
Accepted
time: 0ms
memory: 3884kb
input:
4 4 14.0
output:
5 0.000000 0.000000 0.000000 4.000000 1.000000 4.000000 1.000000 0.000000 4.000000 4.000000
result:
ok correct
Test #38:
score: 0
Accepted
time: 0ms
memory: 3916kb
input:
4 4 14.000002
output:
6 0.000000 0.000000 0.000000 4.000000 1.000000 4.000000 1.000000 0.000000 1.000005 0.000000 4.000000 4.000000
result:
ok correct
Test #39:
score: 0
Accepted
time: 0ms
memory: 3816kb
input:
4 4 15.123104
output:
7 0.000000 0.000000 0.000000 4.000000 1.000000 4.000000 1.000000 0.000000 2.000000 0.000000 2.000000 2.780773 4.000000 4.000000
result:
ok correct
Test #40:
score: 0
Accepted
time: 0ms
memory: 3808kb
input:
4 4 15.123106
output:
7 0.000000 0.000000 0.000000 4.000000 1.000000 4.000000 1.000000 0.000000 2.000000 0.000000 2.000000 2.780777 4.000000 4.000000
result:
ok correct
Test #41:
score: 0
Accepted
time: 0ms
memory: 3764kb
input:
4 4 15.123108
output:
7 0.000000 0.000000 0.000000 4.000000 1.000000 4.000000 1.000000 0.000000 2.000000 0.000000 2.000000 2.780781 4.000000 4.000000
result:
ok correct
Test #42:
score: 0
Accepted
time: 0ms
memory: 3832kb
input:
4 4 14.593385
output:
7 0.000000 0.000000 0.000000 4.000000 1.000000 4.000000 1.000000 0.000000 2.000000 0.000000 2.000000 0.926199 4.000000 4.000000
result:
ok correct
Test #43:
score: 0
Accepted
time: 0ms
memory: 3816kb
input:
4 4 14.593387
output:
7 0.000000 0.000000 0.000000 4.000000 1.000000 4.000000 1.000000 0.000000 2.000000 0.000000 2.000000 0.926212 4.000000 4.000000
result:
ok correct
Test #44:
score: 0
Accepted
time: 0ms
memory: 3808kb
input:
4 4 14.593389
output:
7 0.000000 0.000000 0.000000 4.000000 1.000000 4.000000 1.000000 0.000000 2.000000 0.000000 2.000000 0.926224 4.000000 4.000000
result:
ok correct
Test #45:
score: 0
Accepted
time: 0ms
memory: 3764kb
input:
2 2 4.0
output:
3 0.000000 0.000000 0.000000 2.000000 2.000000 2.000000
result:
ok correct
Test #46:
score: 0
Accepted
time: 0ms
memory: 4060kb
input:
3 3 5.0
output:
3 0.000000 0.000000 0.000000 1.750000 3.000000 3.000000
result:
ok correct
Test #47:
score: 0
Accepted
time: 0ms
memory: 3952kb
input:
4 4 15.123
output:
7 0.000000 0.000000 0.000000 4.000000 1.000000 4.000000 1.000000 0.000000 2.000000 0.000000 2.000000 2.780556 4.000000 4.000000
result:
ok correct
Test #48:
score: 0
Accepted
time: 0ms
memory: 3756kb
input:
4 4 14.1
output:
6 0.000000 0.000000 0.000000 4.000000 1.000000 4.000000 1.000000 0.000000 1.240476 0.000000 4.000000 4.000000
result:
ok correct
Test #49:
score: 0
Accepted
time: 0ms
memory: 3816kb
input:
3 3 9.0
output:
5 0.000000 0.000000 0.000000 3.000000 1.000000 3.000000 1.000000 0.900000 3.000000 3.000000
result:
ok correct
Test #50:
score: 0
Accepted
time: 0ms
memory: 3820kb
input:
4 4 16.0
output:
7 0.000000 0.000000 0.000000 4.000000 1.000000 4.000000 1.000000 0.000000 2.000000 0.000000 2.000000 4.000000 4.000000 4.000000
result:
ok correct