QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#636347 | #2290. Kinking Cables | oxford01# | AC ✓ | 7ms | 4080kb | C++20 | 3.1kb | 2024-10-12 23:29:37 | 2024-10-12 23:29:41 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for (auto i = a; i < (b); ++i)
#define repr(i, a, b) for (auto i = (a) - 1; i >= (b); --i)
#define pb push_back
#define eb emplace_back
#define all(x) begin(x), end(x)
#define sz(x) int((x).size())
using ll = long long;
using pii = pair<int, int>;
using vi = vector<int>;
using vll = vector<ll>;
using vii = vector<pii>;
template<class T>
inline bool cmax(T &a, const T &b) {
return a < b ? a = b, 1 : 0;
}
template<class T>
inline bool cmin(T &a, const T &b) {
return b < a ? a = b, 1 : 0;
}
const int inf = 0x3f3f3f3f;
const ll linf = 1e18;
const double dinf = numeric_limits<double>::infinity();
using ld = long double;
int main() {
cin.tie(0)->sync_with_stdio(0);
cin.exceptions(cin.failbit);
int n, m;
cin >> n >> m;
ld l;
cin >> l;
auto len = [&](vector< pair<ld, ld> > p) {
sort(all(p), [&](const auto &a, const auto &b) {
return a.second < b.second;
});
ld ans = 0;
rep(i, 1, sz(p)) {
ans += hypotl(p[i].first - p[i - 1].first, p[i].second - p[i - 1].second);
}
return ans;
};
vector< pair<ld, ld> > p = {{0, 0}, {n, m}};
ld L = hypotl(n, m);
vector< pair<ld, ld> > q;
if (m % 2 == 1) {
rep(i, 1, m) {
if (i % 2 == 1) {
q.eb(n, i);
} else {
q.eb(0, i);
}
}
} else {
rep(i, 1, m - 1) {
if (i % 2 == 1) {
q.eb(n, i);
} else {
q.eb(0, i);
}
}
q.eb(n, m - 2 + 2.l / 3);
q.eb(0, m - 2 + 4.l / 3);
}
ld lx = 0, ly = 0;
for (auto &[y, x] : q) {
auto tmp = p;
tmp.eb(y, x);
// cerr << len(tmp) << endl;
if (len(tmp) < l - 1e-9) {
p.eb(y, x);
lx = x;
ly = y;
continue;
}
ld ty = ly + (x - lx) / (m - lx) * (n - ly);
ld lo = y, hi = ty;
int invert = 0;
if (lo > hi) {
invert = 1;
swap(lo, hi);
}
while (hi - lo > 1e-9) {
ld mid = (lo + hi) / 2;
tmp = p;
tmp.eb(mid, x);
// cerr << mid << ' ' << len(tmp) << endl;
if (len(tmp) > l) {
if (invert) {
hi = mid;
} else {
lo = mid;
}
} else {
if (invert) {
lo = mid;
} else {
hi = mid;
}
}
}
p.eb(lo, x);
break;
// ld ty = ly + (m - lx) * (m - ly);
}
sort(all(p), [&](const auto &a, const auto &b) {
return a.second < b.second;
});
cout << sz(p) << '\n';
cout << fixed << setprecision(15);
for (auto &[x, y] : p) {
cout << x << ' ' << y << '\n';
}
// cerr << len(p) << endl;
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 4000kb
input:
79 78 1980.7712136406
output:
26 0.000000000000000 0.000000000000000 79.000000000000000 1.000000000000000 0.000000000000000 2.000000000000000 79.000000000000000 3.000000000000000 0.000000000000000 4.000000000000000 79.000000000000000 5.000000000000000 0.000000000000000 6.000000000000000 79.000000000000000 7.000000000000000 0.000...
result:
ok correct
Test #2:
score: 0
Accepted
time: 0ms
memory: 3988kb
input:
33 65 1947.7601065763
output:
60 0.000000000000000 0.000000000000000 33.000000000000000 1.000000000000000 0.000000000000000 2.000000000000000 33.000000000000000 3.000000000000000 0.000000000000000 4.000000000000000 33.000000000000000 5.000000000000000 0.000000000000000 6.000000000000000 33.000000000000000 7.000000000000000 0.000...
result:
ok correct
Test #3:
score: 0
Accepted
time: 1ms
memory: 3972kb
input:
51 51 555.0803652025
output:
12 0.000000000000000 0.000000000000000 51.000000000000000 1.000000000000000 0.000000000000000 2.000000000000000 51.000000000000000 3.000000000000000 0.000000000000000 4.000000000000000 51.000000000000000 5.000000000000000 0.000000000000000 6.000000000000000 51.000000000000000 7.000000000000000 0.000...
result:
ok correct
Test #4:
score: 0
Accepted
time: 1ms
memory: 3992kb
input:
49 2 67.3588717350
output:
4 0.000000000000000 0.000000000000000 49.000000000000000 0.666666666666667 39.847078314764076 1.333333333333333 49.000000000000000 2.000000000000000
result:
ok correct
Test #5:
score: 0
Accepted
time: 1ms
memory: 4020kb
input:
37 48 1713.3643608504
output:
48 0.000000000000000 0.000000000000000 37.000000000000000 1.000000000000000 0.000000000000000 2.000000000000000 37.000000000000000 3.000000000000000 0.000000000000000 4.000000000000000 37.000000000000000 5.000000000000000 0.000000000000000 6.000000000000000 37.000000000000000 7.000000000000000 0.000...
result:
ok correct
Test #6:
score: 0
Accepted
time: 0ms
memory: 4000kb
input:
51 79 820.1218304546
output:
17 0.000000000000000 0.000000000000000 51.000000000000000 1.000000000000000 0.000000000000000 2.000000000000000 51.000000000000000 3.000000000000000 0.000000000000000 4.000000000000000 51.000000000000000 5.000000000000000 0.000000000000000 6.000000000000000 51.000000000000000 7.000000000000000 0.000...
result:
ok correct
Test #7:
score: 0
Accepted
time: 1ms
memory: 3980kb
input:
6 8 37.5338494218
output:
8 0.000000000000000 0.000000000000000 6.000000000000000 1.000000000000000 0.000000000000000 2.000000000000000 6.000000000000000 3.000000000000000 0.000000000000000 4.000000000000000 6.000000000000000 5.000000000000000 2.803421508986503 6.000000000000000 6.000000000000000 8.000000000000000
result:
ok correct
Test #8:
score: 0
Accepted
time: 0ms
memory: 4044kb
input:
5 5 7.1908428511
output:
3 0.000000000000000 0.000000000000000 1.836334371939301 1.000000000000000 5.000000000000000 5.000000000000000
result:
ok correct
Test #9:
score: 0
Accepted
time: 1ms
memory: 3980kb
input:
5 4 8.3927665498
output:
4 0.000000000000000 0.000000000000000 5.000000000000000 1.000000000000000 4.352242964669131 2.000000000000000 5.000000000000000 4.000000000000000
result:
ok correct
Test #10:
score: 0
Accepted
time: 1ms
memory: 3928kb
input:
4 2 6.4617533647
output:
4 0.000000000000000 0.000000000000000 4.000000000000000 0.666666666666667 2.998271299526095 1.333333333333333 4.000000000000000 2.000000000000000
result:
ok correct
Test #11:
score: 0
Accepted
time: 1ms
memory: 4080kb
input:
91 87 4830.8473359767
output:
55 0.000000000000000 0.000000000000000 91.000000000000000 1.000000000000000 0.000000000000000 2.000000000000000 91.000000000000000 3.000000000000000 0.000000000000000 4.000000000000000 91.000000000000000 5.000000000000000 0.000000000000000 6.000000000000000 91.000000000000000 7.000000000000000 0.000...
result:
ok correct
Test #12:
score: 0
Accepted
time: 1ms
memory: 3980kb
input:
90 90 5088.9280941138
output:
58 0.000000000000000 0.000000000000000 90.000000000000000 1.000000000000000 0.000000000000000 2.000000000000000 90.000000000000000 3.000000000000000 0.000000000000000 4.000000000000000 90.000000000000000 5.000000000000000 0.000000000000000 6.000000000000000 90.000000000000000 7.000000000000000 0.000...
result:
ok correct
Test #13:
score: 0
Accepted
time: 1ms
memory: 3948kb
input:
90 92 7004.0153432299
output:
80 0.000000000000000 0.000000000000000 90.000000000000000 1.000000000000000 0.000000000000000 2.000000000000000 90.000000000000000 3.000000000000000 0.000000000000000 4.000000000000000 90.000000000000000 5.000000000000000 0.000000000000000 6.000000000000000 90.000000000000000 7.000000000000000 0.000...
result:
ok correct
Test #14:
score: 0
Accepted
time: 1ms
memory: 3992kb
input:
91 83 1879.3819547895
output:
22 0.000000000000000 0.000000000000000 91.000000000000000 1.000000000000000 0.000000000000000 2.000000000000000 91.000000000000000 3.000000000000000 0.000000000000000 4.000000000000000 91.000000000000000 5.000000000000000 0.000000000000000 6.000000000000000 91.000000000000000 7.000000000000000 0.000...
result:
ok correct
Test #15:
score: 0
Accepted
time: 1ms
memory: 4008kb
input:
3 81 199.2077743610
output:
57 0.000000000000000 0.000000000000000 3.000000000000000 1.000000000000000 0.000000000000000 2.000000000000000 3.000000000000000 3.000000000000000 0.000000000000000 4.000000000000000 3.000000000000000 5.000000000000000 0.000000000000000 6.000000000000000 3.000000000000000 7.000000000000000 0.0000000...
result:
ok correct
Test #16:
score: 0
Accepted
time: 1ms
memory: 3968kb
input:
4 89 288.5915130114
output:
66 0.000000000000000 0.000000000000000 4.000000000000000 1.000000000000000 0.000000000000000 2.000000000000000 4.000000000000000 3.000000000000000 0.000000000000000 4.000000000000000 4.000000000000000 5.000000000000000 0.000000000000000 6.000000000000000 4.000000000000000 7.000000000000000 0.0000000...
result:
ok correct
Test #17:
score: 0
Accepted
time: 1ms
memory: 4044kb
input:
95 3 175.9210001082
output:
4 0.000000000000000 0.000000000000000 95.000000000000000 1.000000000000000 54.554491874987434 2.000000000000000 95.000000000000000 3.000000000000000
result:
ok correct
Test #18:
score: 0
Accepted
time: 0ms
memory: 4056kb
input:
84 4 310.3037172015
output:
6 0.000000000000000 0.000000000000000 84.000000000000000 1.000000000000000 0.000000000000000 2.000000000000000 84.000000000000000 2.666666666666667 54.863042118027806 3.333333333333333 84.000000000000000 4.000000000000000
result:
ok correct
Test #19:
score: 0
Accepted
time: 0ms
memory: 3916kb
input:
2 2 2.8284271248
output:
3 0.000000000000000 0.000000000000000 0.666678297643860 0.666666666666667 2.000000000000000 2.000000000000000
result:
ok correct
Test #20:
score: 0
Accepted
time: 1ms
memory: 4068kb
input:
100 100 10000.0000000000
output:
102 0.000000000000000 0.000000000000000 100.000000000000000 1.000000000000000 0.000000000000000 2.000000000000000 100.000000000000000 3.000000000000000 0.000000000000000 4.000000000000000 100.000000000000000 5.000000000000000 0.000000000000000 6.000000000000000 100.000000000000000 7.000000000000000 ...
result:
ok correct
Test #21:
score: 0
Accepted
time: 1ms
memory: 3960kb
input:
100 100 9999.2500000000
output:
102 0.000000000000000 0.000000000000000 100.000000000000000 1.000000000000000 0.000000000000000 2.000000000000000 100.000000000000000 3.000000000000000 0.000000000000000 4.000000000000000 100.000000000000000 5.000000000000000 0.000000000000000 6.000000000000000 100.000000000000000 7.000000000000000 ...
result:
ok correct
Test #22:
score: 0
Accepted
time: 1ms
memory: 3960kb
input:
100 100 2723.8981892905
output:
28 0.000000000000000 0.000000000000000 100.000000000000000 1.000000000000000 0.000000000000000 2.000000000000000 100.000000000000000 3.000000000000000 0.000000000000000 4.000000000000000 100.000000000000000 5.000000000000000 0.000000000000000 6.000000000000000 100.000000000000000 7.000000000000000 0...
result:
ok correct
Test #23:
score: 0
Accepted
time: 0ms
memory: 4028kb
input:
100 100 8994.4904261819
output:
92 0.000000000000000 0.000000000000000 100.000000000000000 1.000000000000000 0.000000000000000 2.000000000000000 100.000000000000000 3.000000000000000 0.000000000000000 4.000000000000000 100.000000000000000 5.000000000000000 0.000000000000000 6.000000000000000 100.000000000000000 7.000000000000000 0...
result:
ok correct
Test #24:
score: 0
Accepted
time: 0ms
memory: 3968kb
input:
100 100 881.4998747190
output:
10 0.000000000000000 0.000000000000000 100.000000000000000 1.000000000000000 0.000000000000000 2.000000000000000 100.000000000000000 3.000000000000000 0.000000000000000 4.000000000000000 100.000000000000000 5.000000000000000 0.000000000000000 6.000000000000000 100.000000000000000 7.000000000000000 3...
result:
ok correct
Test #25:
score: 0
Accepted
time: 0ms
memory: 4032kb
input:
88 94 8266.2500000000
output:
96 0.000000000000000 0.000000000000000 88.000000000000000 1.000000000000000 0.000000000000000 2.000000000000000 88.000000000000000 3.000000000000000 0.000000000000000 4.000000000000000 88.000000000000000 5.000000000000000 0.000000000000000 6.000000000000000 88.000000000000000 7.000000000000000 0.000...
result:
ok correct
Test #26:
score: 0
Accepted
time: 0ms
memory: 3916kb
input:
75 37 2772.0000000000
output:
38 0.000000000000000 0.000000000000000 75.000000000000000 1.000000000000000 0.000000000000000 2.000000000000000 75.000000000000000 3.000000000000000 0.000000000000000 4.000000000000000 75.000000000000000 5.000000000000000 0.000000000000000 6.000000000000000 75.000000000000000 7.000000000000000 0.000...
result:
ok correct
Test #27:
score: 0
Accepted
time: 1ms
memory: 4048kb
input:
48 39 62.0000000000
output:
3 0.000000000000000 0.000000000000000 2.659090908781554 1.000000000000000 48.000000000000000 39.000000000000000
result:
ok correct
Test #28:
score: 0
Accepted
time: 1ms
memory: 3972kb
input:
98 94 135.9000000000
output:
3 0.000000000000000 0.000000000000000 2.022096045488650 1.000000000000000 98.000000000000000 94.000000000000000
result:
ok correct
Test #29:
score: 0
Accepted
time: 1ms
memory: 4004kb
input:
90 81 7290.0000000000
output:
82 0.000000000000000 0.000000000000000 90.000000000000000 1.000000000000000 0.000000000000000 2.000000000000000 90.000000000000000 3.000000000000000 0.000000000000000 4.000000000000000 90.000000000000000 5.000000000000000 0.000000000000000 6.000000000000000 90.000000000000000 7.000000000000000 0.000...
result:
ok correct
Test #30:
score: 0
Accepted
time: 1ms
memory: 3900kb
input:
90 81 121.0826164250
output:
3 0.000000000000000 0.000000000000000 1.111205023351229 1.000000000000000 90.000000000000000 81.000000000000000
result:
ok correct
Test #31:
score: 0
Accepted
time: 1ms
memory: 4028kb
input:
34 99 3366.0000000000
output:
100 0.000000000000000 0.000000000000000 34.000000000000000 1.000000000000000 0.000000000000000 2.000000000000000 34.000000000000000 3.000000000000000 0.000000000000000 4.000000000000000 34.000000000000000 5.000000000000000 0.000000000000000 6.000000000000000 34.000000000000000 7.000000000000000 0.00...
result:
ok correct
Test #32:
score: 0
Accepted
time: 1ms
memory: 3972kb
input:
34 99 104.6756896330
output:
3 0.000000000000000 0.000000000000000 0.343474483798314 1.000000000000000 34.000000000000000 99.000000000000000
result:
ok correct
Test #33:
score: 0
Accepted
time: 1ms
memory: 3980kb
input:
3 3 5.9999
output:
4 0.000000000000000 0.000000000000000 3.000000000000000 1.000000000000000 1.993508501211181 2.000000000000000 3.000000000000000 3.000000000000000
result:
ok correct
Test #34:
score: 0
Accepted
time: 1ms
memory: 3968kb
input:
3 3 6.0
output:
4 0.000000000000000 0.000000000000000 3.000000000000000 1.000000000000000 1.993438019882888 2.000000000000000 3.000000000000000 3.000000000000000
result:
ok correct
Test #35:
score: 0
Accepted
time: 1ms
memory: 3996kb
input:
3 3 6.0001
output:
4 0.000000000000000 0.000000000000000 3.000000000000000 1.000000000000000 1.993367540650070 2.000000000000000 3.000000000000000 3.000000000000000
result:
ok correct
Test #36:
score: 0
Accepted
time: 1ms
memory: 3964kb
input:
4 4 13.999998
output:
6 0.000000000000000 0.000000000000000 4.000000000000000 1.000000000000000 0.000000000000000 2.000000000000000 4.000000000000000 2.666666666666667 3.473809913732111 3.333333333333333 4.000000000000000 4.000000000000000
result:
ok correct
Test #37:
score: 0
Accepted
time: 1ms
memory: 3972kb
input:
4 4 14.0
output:
6 0.000000000000000 0.000000000000000 4.000000000000000 1.000000000000000 0.000000000000000 2.000000000000000 4.000000000000000 2.666666666666667 3.473808299750090 3.333333333333333 4.000000000000000 4.000000000000000
result:
ok correct
Test #38:
score: 0
Accepted
time: 1ms
memory: 3988kb
input:
4 4 14.000002
output:
6 0.000000000000000 0.000000000000000 4.000000000000000 1.000000000000000 0.000000000000000 2.000000000000000 4.000000000000000 2.666666666666667 3.473806685768068 3.333333333333333 4.000000000000000 4.000000000000000
result:
ok correct
Test #39:
score: 0
Accepted
time: 1ms
memory: 3988kb
input:
4 4 15.123104
output:
6 0.000000000000000 0.000000000000000 4.000000000000000 1.000000000000000 0.000000000000000 2.000000000000000 4.000000000000000 2.666666666666667 2.756586033850908 3.333333333333333 4.000000000000000 4.000000000000000
result:
ok correct
Test #40:
score: 0
Accepted
time: 0ms
memory: 3976kb
input:
4 4 15.123106
output:
6 0.000000000000000 0.000000000000000 4.000000000000000 1.000000000000000 0.000000000000000 2.000000000000000 4.000000000000000 2.666666666666667 2.756584898568690 3.333333333333333 4.000000000000000 4.000000000000000
result:
ok correct
Test #41:
score: 0
Accepted
time: 1ms
memory: 3964kb
input:
4 4 15.123108
output:
6 0.000000000000000 0.000000000000000 4.000000000000000 1.000000000000000 0.000000000000000 2.000000000000000 4.000000000000000 2.666666666666667 2.756583764217794 3.333333333333333 4.000000000000000 4.000000000000000
result:
ok correct
Test #42:
score: 0
Accepted
time: 1ms
memory: 3976kb
input:
4 4 14.593385
output:
6 0.000000000000000 0.000000000000000 4.000000000000000 1.000000000000000 0.000000000000000 2.000000000000000 4.000000000000000 2.666666666666667 3.067867982201278 3.333333333333333 4.000000000000000 4.000000000000000
result:
ok correct
Test #43:
score: 0
Accepted
time: 0ms
memory: 3972kb
input:
4 4 14.593387
output:
6 0.000000000000000 0.000000000000000 4.000000000000000 1.000000000000000 0.000000000000000 2.000000000000000 4.000000000000000 2.666666666666667 3.067866751924157 3.333333333333333 4.000000000000000 4.000000000000000
result:
ok correct
Test #44:
score: 0
Accepted
time: 1ms
memory: 3912kb
input:
4 4 14.593389
output:
6 0.000000000000000 0.000000000000000 4.000000000000000 1.000000000000000 0.000000000000000 2.000000000000000 4.000000000000000 2.666666666666667 3.067865522578359 3.333333333333333 4.000000000000000 4.000000000000000
result:
ok correct
Test #45:
score: 0
Accepted
time: 0ms
memory: 3984kb
input:
2 2 4.0
output:
4 0.000000000000000 0.000000000000000 2.000000000000000 0.666666666666667 1.328958679921925 1.333333333333333 2.000000000000000 2.000000000000000
result:
ok correct
Test #46:
score: 0
Accepted
time: 7ms
memory: 3996kb
input:
3 3 5.0
output:
3 0.000000000000000 0.000000000000000 2.819836056791246 1.000000000000000 3.000000000000000 3.000000000000000
result:
ok correct
Test #47:
score: 0
Accepted
time: 1ms
memory: 3868kb
input:
4 4 15.123
output:
6 0.000000000000000 0.000000000000000 4.000000000000000 1.000000000000000 0.000000000000000 2.000000000000000 4.000000000000000 2.666666666666667 2.756645036861300 3.333333333333333 4.000000000000000 4.000000000000000
result:
ok correct
Test #48:
score: 0
Accepted
time: 0ms
memory: 3996kb
input:
4 4 14.1
output:
6 0.000000000000000 0.000000000000000 4.000000000000000 1.000000000000000 0.000000000000000 2.000000000000000 4.000000000000000 2.666666666666667 3.396420351229608 3.333333333333333 4.000000000000000 4.000000000000000
result:
ok correct
Test #49:
score: 0
Accepted
time: 1ms
memory: 3960kb
input:
3 3 9.0
output:
4 0.000000000000000 0.000000000000000 3.000000000000000 1.000000000000000 0.257783645996824 2.000000000000000 3.000000000000000 3.000000000000000
result:
ok correct
Test #50:
score: 0
Accepted
time: 0ms
memory: 3980kb
input:
4 4 16.0
output:
6 0.000000000000000 0.000000000000000 4.000000000000000 1.000000000000000 0.000000000000000 2.000000000000000 4.000000000000000 2.666666666666667 2.275038714520633 3.333333333333333 4.000000000000000 4.000000000000000
result:
ok correct