QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#305886 | #2290. Kinking Cables | ckiseki | AC ✓ | 1ms | 4096kb | C++20 | 2.7kb | 2024-01-16 05:47:11 | 2024-01-16 05:47:11 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
const int inf = 1e9;
using ll = int64_t;
using llf = long double;
const llf eps = 1e-8;
int n, m;
llf len;
bool in(llf x, llf L, llf R) {
if (L > R)
swap(L, R);
return L <= x && x <= R;
}
long double dc(const function<llf(llf)> &func,
llf l, llf r, llf fl, llf fr) {
llf m = (l + r) / 2;
llf fm = func(m);
if (abs(fm - len) < eps) {
return m;
}
if (in(len, fm, fl))
return dc(func, l, m, fl, fm);
else
return dc(func, m, r, fm, fr);
}
pair<long double, bool>
proc(const function<llf(llf)> &func, llf l, llf r) {
llf fl = func(l), fr = func(r);
if (in(len, fl, fr)) {
return { dc(func, l, r, fl, fr), true };
} else {
return { -1, false };
}
}
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> m >> len;
vector<pair<llf,llf>> seg;
const auto Output = [&seg]() {
seg.emplace_back(n, m);
// llf tot = 0;
// for (int i = 1; i < (int)seg.size(); i++) {
// auto [x1, y1] = seg[i-1];
// auto [x2, y2] = seg[i];
// tot += hypot(x1-x2, y1-y2);
// }
// cerr << tot << endl;
cout << seg.size() << '\n';
cout << fixed << setprecision(10);
for (auto [x, y]: seg) {
cout << x << ' ' << y << '\n';
}
exit(0);
};
int len = 0;
llf res;
bool succ;
for (int i = 0; i < n; i++) {
if (i % 2 == 0) {
seg.emplace_back(i, 0);
tie(res, succ) = proc([&](llf t) {
return len + t + hypot(n - i, m - (0 + t));
}, 0, m);
if (succ) {
seg.emplace_back(i, 0 + res);
Output();
}
seg.emplace_back(i, m);
tie(res, succ) = proc([&](llf t) {
return len + m + t + hypot(n - (i + t), m - m);
}, 0, 1);
if (succ) {
seg.emplace_back(i + res, m);
Output();
}
} else {
seg.emplace_back(i, m);
tie(res, succ) = proc([&](llf t) {
return len + t + hypot(n - i, m - (m - t));
}, 0, m);
if (succ) {
seg.emplace_back(i, m - res);
Output();
}
seg.emplace_back(i, 0);
tie(res, succ) = proc([&](llf t) {
return len + m + t + hypot(n - (i + t), m - 0);
}, 0, 1);
if (succ) {
seg.emplace_back(i + res, 0);
Output();
}
}
len += 1 + m;
}
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 4068kb
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: 1ms
memory: 3992kb
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: 0ms
memory: 4068kb
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: 3936kb
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: 0ms
memory: 4000kb
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: 0ms
memory: 3976kb
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: 0ms
memory: 3984kb
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.1602695435 6.0000000000 8.0000000000
result:
ok correct
Test #8:
score: 0
Accepted
time: 0ms
memory: 4008kb
input:
5 5 7.1908428511
output:
3 0.0000000000 0.0000000000 0.0000000000 0.3898547590 5.0000000000 5.0000000000
result:
ok correct
Test #9:
score: 0
Accepted
time: 0ms
memory: 4060kb
input:
5 4 8.3927665498
output:
3 0.0000000000 0.0000000000 0.0000000000 3.3507961333 5.0000000000 4.0000000000
result:
ok correct
Test #10:
score: 0
Accepted
time: 0ms
memory: 4008kb
input:
4 2 6.4617533647
output:
5 0.0000000000 0.0000000000 0.0000000000 2.0000000000 1.0000000000 2.0000000000 1.0000000000 1.5690426230 4.0000000000 2.0000000000
result:
ok correct
Test #11:
score: 0
Accepted
time: 1ms
memory: 4020kb
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: 1ms
memory: 3984kb
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: 1ms
memory: 3976kb
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: 1ms
memory: 3984kb
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: 1ms
memory: 3928kb
input:
3 81 199.2077743610
output:
5 0.0000000000 0.0000000000 0.0000000000 81.0000000000 1.0000000000 81.0000000000 1.0000000000 22.4131765306 3.0000000000 81.0000000000
result:
ok correct
Test #16:
score: 0
Accepted
time: 0ms
memory: 3940kb
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.7311374912 4.0000000000 89.0000000000
result:
ok correct
Test #17:
score: 0
Accepted
time: 1ms
memory: 4012kb
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: 1ms
memory: 3940kb
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: 3972kb
input:
2 2 2.8284271248
output:
3 0.0000000000 0.0000000000 0.0000000000 0.0000000298 2.0000000000 2.0000000000
result:
ok correct
Test #20:
score: 0
Accepted
time: 0ms
memory: 4092kb
input:
100 100 10000.0000000000
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 #21:
score: 0
Accepted
time: 1ms
memory: 3944kb
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: 1ms
memory: 3936kb
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: 3996kb
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: 0ms
memory: 3996kb
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: 1ms
memory: 4012kb
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: 4096kb
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: 0ms
memory: 3940kb
input:
48 39 62.0000000000
output:
3 0.0000000000 0.0000000000 0.0000000000 0.4130434915 48.0000000000 39.0000000000
result:
ok correct
Test #28:
score: 0
Accepted
time: 1ms
memory: 3980kb
input:
98 94 135.9000000000
output:
3 0.0000000000 0.0000000000 0.0000000000 0.3437947817 98.0000000000 94.0000000000
result:
ok correct
Test #29:
score: 0
Accepted
time: 1ms
memory: 4092kb
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: 3924kb
input:
90 81 121.0826164250
output:
3 0.0000000000 0.0000000000 0.0000000000 0.0000000189 90.0000000000 81.0000000000
result:
ok correct
Test #31:
score: 0
Accepted
time: 1ms
memory: 3996kb
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: 0ms
memory: 3924kb
input:
34 99 104.6756896330
output:
3 0.0000000000 0.0000000000 0.0000000000 0.0000001844 34.0000000000 99.0000000000
result:
ok correct
Test #33:
score: 0
Accepted
time: 0ms
memory: 3996kb
input:
3 3 5.9999
output:
3 0.0000000000 0.0000000000 0.0000000000 2.9998999983 3.0000000000 3.0000000000
result:
ok correct
Test #34:
score: 0
Accepted
time: 1ms
memory: 3940kb
input:
3 3 6.0
output:
3 0.0000000000 0.0000000000 0.0000000000 2.9999999944 3.0000000000 3.0000000000
result:
ok correct
Test #35:
score: 0
Accepted
time: 0ms
memory: 3996kb
input:
3 3 6.0001
output:
5 0.0000000000 0.0000000000 0.0000000000 3.0000000000 1.0000000000 3.0000000000 1.0000000000 2.9998999983 3.0000000000 3.0000000000
result:
ok correct
Test #36:
score: 0
Accepted
time: 0ms
memory: 3980kb
input:
4 4 13.999998
output:
5 0.0000000000 0.0000000000 0.0000000000 4.0000000000 1.0000000000 4.0000000000 1.0000000000 0.0000011101 4.0000000000 4.0000000000
result:
ok correct
Test #37:
score: 0
Accepted
time: 1ms
memory: 3976kb
input:
4 4 14.0
output:
5 0.0000000000 0.0000000000 0.0000000000 4.0000000000 1.0000000000 4.0000000000 1.0000000000 0.0000000037 4.0000000000 4.0000000000
result:
ok correct
Test #38:
score: 0
Accepted
time: 1ms
memory: 4060kb
input:
4 4 14.000002
output:
6 0.0000000000 0.0000000000 0.0000000000 4.0000000000 1.0000000000 4.0000000000 1.0000000000 0.0000000000 1.0000050068 0.0000000000 4.0000000000 4.0000000000
result:
ok correct
Test #39:
score: 0
Accepted
time: 1ms
memory: 4004kb
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.7807730138 4.0000000000 4.0000000000
result:
ok correct
Test #40:
score: 0
Accepted
time: 1ms
memory: 4012kb
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.7807771862 4.0000000000 4.0000000000
result:
ok correct
Test #41:
score: 0
Accepted
time: 0ms
memory: 4004kb
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.7807813585 4.0000000000 4.0000000000
result:
ok correct
Test #42:
score: 0
Accepted
time: 1ms
memory: 3944kb
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.9261994362 4.0000000000 4.0000000000
result:
ok correct
Test #43:
score: 0
Accepted
time: 0ms
memory: 3976kb
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.9262118340 4.0000000000 4.0000000000
result:
ok correct
Test #44:
score: 0
Accepted
time: 1ms
memory: 4008kb
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.9262242317 4.0000000000 4.0000000000
result:
ok correct
Test #45:
score: 0
Accepted
time: 0ms
memory: 3976kb
input:
2 2 4.0
output:
3 0.0000000000 0.0000000000 0.0000000000 1.9999999925 2.0000000000 2.0000000000
result:
ok correct
Test #46:
score: 0
Accepted
time: 0ms
memory: 3972kb
input:
3 3 5.0
output:
3 0.0000000000 0.0000000000 0.0000000000 1.7499999851 3.0000000000 3.0000000000
result:
ok correct
Test #47:
score: 0
Accepted
time: 0ms
memory: 3972kb
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.7805560827 4.0000000000 4.0000000000
result:
ok correct
Test #48:
score: 0
Accepted
time: 1ms
memory: 3992kb
input:
4 4 14.1
output:
6 0.0000000000 0.0000000000 0.0000000000 4.0000000000 1.0000000000 4.0000000000 1.0000000000 0.0000000000 1.2404761910 0.0000000000 4.0000000000 4.0000000000
result:
ok correct
Test #49:
score: 0
Accepted
time: 0ms
memory: 4004kb
input:
3 3 9.0
output:
5 0.0000000000 0.0000000000 0.0000000000 3.0000000000 1.0000000000 3.0000000000 1.0000000000 0.9000000022 3.0000000000 3.0000000000
result:
ok correct
Test #50:
score: 0
Accepted
time: 0ms
memory: 3976kb
input:
4 4 16.0
output:
7 0.0000000000 0.0000000000 0.0000000000 4.0000000000 1.0000000000 4.0000000000 1.0000000000 0.0000000000 2.0000000000 0.0000000000 2.0000000000 3.9999999925 4.0000000000 4.0000000000
result:
ok correct