QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#31494 | #2290. Kinking Cables | Vingying0# | AC ✓ | 6ms | 3916kb | C++17 | 2.4kb | 2022-05-08 14:44:23 | 2022-05-08 14:44:24 |
Judging History
answer
#include "bits/stdc++.h"
using namespace std;
const int N = 105;
using db = long double;
int n, m;
db len;
using pdb = pair<db, db>;
vector<pdb> ans;
const db eps = 1e-9;
int dcmp(const db &x) {
return abs(x) < 1e-5?0:(x < 0?-1:1);
}
db x = 0, y = 0, lx = 0, ly = 0;
db dist(db x,db y, db _x,db _y) {
return sqrtl((x-_x)*(x-_x)+(y-_y)*(y-_y));
}
void add(db x, db y) {
::x = x, ::y = y;
ans.push_back({x, y});
len -= dist(::x, ::y, lx, ly);
lx = x, ly = y;
}
void solve()
{
add(x, y);
int f = 0;
while (len > 1e-9)
{
if (f == 0) {
if (dcmp(n + m - x - len) != -1) {
db mx = (x + m) / 2, my = (y + n) / 2;
db d = dist(mx, my, m, 0);
db vx = -(m - mx) / d, vy = my / d;
db l = 0, r = d;
db nx, ny;
while((r - l)>eps) {
db mid = (l + r) / 2;
nx = m + vx * mid, ny = vy * mid;
if (dist(nx, ny, x, y) + dist(nx, ny, m, n) > len) {
l = mid;
}
else r = mid;
}
add(nx, ny);
break;
}
else {
y = n;
add(x, y);
}
} else {
if (dcmp(sqrt(1+n*n)+dist(x+1,0,m,n) - len) != -1) {
db mx = x + 1, my = y;
db vx = 0, vy = -1;
db l = 0, r = n;
db nx, ny;
while((r - l)>eps) {
db mid = (l + r) / 2;
nx = mx + vx * mid, ny = my + vy * mid;
if (dist(nx, ny, x, y) + dist(nx, ny, m, n) < len) {
l = mid;
}
else r = mid;
}
add(nx, ny);
break;
}
else {
x++, y=0;
add(x, y);
}
}
f ^= 1;
}
add(m, n);
}
int main()
{
cout << fixed << setprecision(10);
cin >> n >> m >> len;
solve();
cout << ans.size() << "\n";
for (auto [px, py] : ans)
{
cout << py << " " << px << "\n";
}
cout.flush();
assert(dcmp(len) == 0);
// cerr << len << endl;
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 3788kb
input:
79 78 1980.7712136406
output:
26 0.0000000000 0.0000000000 79.0000000000 0.0000000000 0.0000000000 1.0000000000 79.0000000000 1.0000000000 0.0000000000 2.0000000000 79.0000000000 2.0000000000 0.0000000000 3.0000000000 79.0000000000 3.0000000000 0.0000000000 4.0000000000 79.0000000000 4.0000000000 0.0000000000 5.0000000000 79.000...
result:
ok correct
Test #2:
score: 0
Accepted
time: 2ms
memory: 3704kb
input:
33 65 1947.7601065763
output:
60 0.0000000000 0.0000000000 33.0000000000 0.0000000000 0.0000000000 1.0000000000 33.0000000000 1.0000000000 0.0000000000 2.0000000000 33.0000000000 2.0000000000 0.0000000000 3.0000000000 33.0000000000 3.0000000000 0.0000000000 4.0000000000 33.0000000000 4.0000000000 0.0000000000 5.0000000000 33.000...
result:
ok correct
Test #3:
score: 0
Accepted
time: 3ms
memory: 3820kb
input:
51 51 555.0803652025
output:
12 0.0000000000 0.0000000000 51.0000000000 0.0000000000 0.0000000000 1.0000000000 51.0000000000 1.0000000000 0.0000000000 2.0000000000 51.0000000000 2.0000000000 0.0000000000 3.0000000000 51.0000000000 3.0000000000 0.0000000000 4.0000000000 51.0000000000 4.0000000000 14.0038406518 5.0000000000 51.00...
result:
ok correct
Test #4:
score: 0
Accepted
time: 3ms
memory: 3776kb
input:
49 2 67.3588717350
output:
4 0.0000000000 0.0000000000 49.0000000000 0.0000000000 39.8751962847 1.0000000000 49.0000000000 2.0000000000
result:
ok correct
Test #5:
score: 0
Accepted
time: 3ms
memory: 3852kb
input:
37 48 1713.3643608504
output:
48 0.0000000000 0.0000000000 37.0000000000 0.0000000000 0.0000000000 1.0000000000 37.0000000000 1.0000000000 0.0000000000 2.0000000000 37.0000000000 2.0000000000 0.0000000000 3.0000000000 37.0000000000 3.0000000000 0.0000000000 4.0000000000 37.0000000000 4.0000000000 0.0000000000 5.0000000000 37.000...
result:
ok correct
Test #6:
score: 0
Accepted
time: 3ms
memory: 3708kb
input:
51 79 820.1218304546
output:
17 0.0000000000 0.0000000000 51.0000000000 0.0000000000 0.0000000000 1.0000000000 51.0000000000 1.0000000000 0.0000000000 2.0000000000 51.0000000000 2.0000000000 0.0000000000 3.0000000000 51.0000000000 3.0000000000 0.0000000000 4.0000000000 51.0000000000 4.0000000000 0.0000000000 5.0000000000 51.000...
result:
ok correct
Test #7:
score: 0
Accepted
time: 3ms
memory: 3820kb
input:
6 8 37.5338494218
output:
8 0.0000000000 0.0000000000 6.0000000000 0.0000000000 0.0000000000 1.0000000000 6.0000000000 1.0000000000 0.0000000000 2.0000000000 6.0000000000 2.0000000000 4.2040697455 3.0000000000 6.0000000000 8.0000000000
result:
ok correct
Test #8:
score: 0
Accepted
time: 3ms
memory: 3736kb
input:
5 5 7.1908428511
output:
3 0.0000000000 0.0000000000 2.0379095181 2.9620904819 5.0000000000 5.0000000000
result:
ok correct
Test #9:
score: 0
Accepted
time: 3ms
memory: 3768kb
input:
5 4 8.3927665498
output:
3 0.0000000000 0.0000000000 0.3512614529 3.7189908377 5.0000000000 4.0000000000
result:
ok correct
Test #10:
score: 0
Accepted
time: 3ms
memory: 3756kb
input:
4 2 6.4617533647
output:
4 0.0000000000 0.0000000000 4.0000000000 0.0000000000 3.2823249986 1.0000000000 4.0000000000 2.0000000000
result:
ok correct
Test #11:
score: 0
Accepted
time: 1ms
memory: 3736kb
input:
91 87 4830.8473359767
output:
54 0.0000000000 0.0000000000 91.0000000000 0.0000000000 0.0000000000 1.0000000000 91.0000000000 1.0000000000 0.0000000000 2.0000000000 91.0000000000 2.0000000000 0.0000000000 3.0000000000 91.0000000000 3.0000000000 0.0000000000 4.0000000000 91.0000000000 4.0000000000 0.0000000000 5.0000000000 91.000...
result:
ok correct
Test #12:
score: 0
Accepted
time: 3ms
memory: 3852kb
input:
90 90 5088.9280941138
output:
58 0.0000000000 0.0000000000 90.0000000000 0.0000000000 0.0000000000 1.0000000000 90.0000000000 1.0000000000 0.0000000000 2.0000000000 90.0000000000 2.0000000000 0.0000000000 3.0000000000 90.0000000000 3.0000000000 0.0000000000 4.0000000000 90.0000000000 4.0000000000 0.0000000000 5.0000000000 90.000...
result:
ok correct
Test #13:
score: 0
Accepted
time: 3ms
memory: 3792kb
input:
90 92 7004.0153432299
output:
80 0.0000000000 0.0000000000 90.0000000000 0.0000000000 0.0000000000 1.0000000000 90.0000000000 1.0000000000 0.0000000000 2.0000000000 90.0000000000 2.0000000000 0.0000000000 3.0000000000 90.0000000000 3.0000000000 0.0000000000 4.0000000000 90.0000000000 4.0000000000 0.0000000000 5.0000000000 90.000...
result:
ok correct
Test #14:
score: 0
Accepted
time: 2ms
memory: 3768kb
input:
91 83 1879.3819547895
output:
22 0.0000000000 0.0000000000 91.0000000000 0.0000000000 0.0000000000 1.0000000000 91.0000000000 1.0000000000 0.0000000000 2.0000000000 91.0000000000 2.0000000000 0.0000000000 3.0000000000 91.0000000000 3.0000000000 0.0000000000 4.0000000000 91.0000000000 4.0000000000 0.0000000000 5.0000000000 91.000...
result:
ok correct
Test #15:
score: 0
Accepted
time: 3ms
memory: 3656kb
input:
3 81 199.2077743610
output:
48 0.0000000000 0.0000000000 3.0000000000 0.0000000000 0.0000000000 1.0000000000 3.0000000000 1.0000000000 0.0000000000 2.0000000000 3.0000000000 2.0000000000 0.0000000000 3.0000000000 3.0000000000 3.0000000000 0.0000000000 4.0000000000 3.0000000000 4.0000000000 0.0000000000 5.0000000000 3.000000000...
result:
ok correct
Test #16:
score: 0
Accepted
time: 3ms
memory: 3740kb
input:
4 89 288.5915130114
output:
59 0.0000000000 0.0000000000 4.0000000000 0.0000000000 0.0000000000 1.0000000000 4.0000000000 1.0000000000 0.0000000000 2.0000000000 4.0000000000 2.0000000000 0.0000000000 3.0000000000 4.0000000000 3.0000000000 0.0000000000 4.0000000000 4.0000000000 4.0000000000 0.0000000000 5.0000000000 4.000000000...
result:
ok correct
Test #17:
score: 0
Accepted
time: 3ms
memory: 3652kb
input:
95 3 175.9210001082
output:
4 0.0000000000 0.0000000000 95.0000000000 0.0000000000 54.5704018294 1.0000000000 95.0000000000 3.0000000000
result:
ok correct
Test #18:
score: 0
Accepted
time: 1ms
memory: 3784kb
input:
84 4 310.3037172015
output:
6 0.0000000000 0.0000000000 84.0000000000 0.0000000000 0.0000000000 1.0000000000 84.0000000000 1.0000000000 54.8940209935 2.0000000000 84.0000000000 4.0000000000
result:
ok correct
Test #19:
score: 0
Accepted
time: 6ms
memory: 3916kb
input:
2 2 2.8284271248
output:
3 0.0000000000 0.0000000000 0.9999938314 1.0000061686 2.0000000000 2.0000000000
result:
ok correct
Test #20:
score: 0
Accepted
time: 3ms
memory: 3708kb
input:
100 100 10000.0000000000
output:
102 0.0000000000 0.0000000000 100.0000000000 0.0000000000 0.0000000000 1.0000000000 100.0000000000 1.0000000000 0.0000000000 2.0000000000 100.0000000000 2.0000000000 0.0000000000 3.0000000000 100.0000000000 3.0000000000 0.0000000000 4.0000000000 100.0000000000 4.0000000000 0.0000000000 5.0000000000 ...
result:
ok correct
Test #21:
score: 0
Accepted
time: 3ms
memory: 3788kb
input:
100 100 9999.2500000000
output:
102 0.0000000000 0.0000000000 100.0000000000 0.0000000000 0.0000000000 1.0000000000 100.0000000000 1.0000000000 0.0000000000 2.0000000000 100.0000000000 2.0000000000 0.0000000000 3.0000000000 100.0000000000 3.0000000000 0.0000000000 4.0000000000 100.0000000000 4.0000000000 0.0000000000 5.0000000000 ...
result:
ok correct
Test #22:
score: 0
Accepted
time: 0ms
memory: 3780kb
input:
100 100 2723.8981892905
output:
28 0.0000000000 0.0000000000 100.0000000000 0.0000000000 0.0000000000 1.0000000000 100.0000000000 1.0000000000 0.0000000000 2.0000000000 100.0000000000 2.0000000000 0.0000000000 3.0000000000 100.0000000000 3.0000000000 0.0000000000 4.0000000000 100.0000000000 4.0000000000 0.0000000000 5.0000000000 1...
result:
ok correct
Test #23:
score: 0
Accepted
time: 3ms
memory: 3660kb
input:
100 100 8994.4904261819
output:
92 0.0000000000 0.0000000000 100.0000000000 0.0000000000 0.0000000000 1.0000000000 100.0000000000 1.0000000000 0.0000000000 2.0000000000 100.0000000000 2.0000000000 0.0000000000 3.0000000000 100.0000000000 3.0000000000 0.0000000000 4.0000000000 100.0000000000 4.0000000000 0.0000000000 5.0000000000 1...
result:
ok correct
Test #24:
score: 0
Accepted
time: 0ms
memory: 3784kb
input:
100 100 881.4998747190
output:
10 0.0000000000 0.0000000000 100.0000000000 0.0000000000 0.0000000000 1.0000000000 100.0000000000 1.0000000000 0.0000000000 2.0000000000 100.0000000000 2.0000000000 0.0000000000 3.0000000000 100.0000000000 3.0000000000 34.6530040340 4.0000000000 100.0000000000 100.0000000000
result:
ok correct
Test #25:
score: 0
Accepted
time: 3ms
memory: 3868kb
input:
88 94 8266.2500000000
output:
96 0.0000000000 0.0000000000 88.0000000000 0.0000000000 0.0000000000 1.0000000000 88.0000000000 1.0000000000 0.0000000000 2.0000000000 88.0000000000 2.0000000000 0.0000000000 3.0000000000 88.0000000000 3.0000000000 0.0000000000 4.0000000000 88.0000000000 4.0000000000 0.0000000000 5.0000000000 88.000...
result:
ok correct
Test #26:
score: 0
Accepted
time: 3ms
memory: 3852kb
input:
75 37 2772.0000000000
output:
38 0.0000000000 0.0000000000 75.0000000000 0.0000000000 0.0000000000 1.0000000000 75.0000000000 1.0000000000 0.0000000000 2.0000000000 75.0000000000 2.0000000000 0.0000000000 3.0000000000 75.0000000000 3.0000000000 0.0000000000 4.0000000000 75.0000000000 4.0000000000 0.0000000000 5.0000000000 75.000...
result:
ok correct
Test #27:
score: 0
Accepted
time: 2ms
memory: 3648kb
input:
48 39 62.0000000000
output:
3 0.0000000000 0.0000000000 22.2720905354 20.9039264400 48.0000000000 39.0000000000
result:
ok correct
Test #28:
score: 0
Accepted
time: 0ms
memory: 3716kb
input:
98 94 135.9000000000
output:
3 0.0000000000 0.0000000000 47.0615096025 48.8593683404 98.0000000000 94.0000000000
result:
ok correct
Test #29:
score: 0
Accepted
time: 0ms
memory: 3692kb
input:
90 81 7290.0000000000
output:
82 0.0000000000 0.0000000000 90.0000000000 0.0000000000 0.0000000000 1.0000000000 90.0000000000 1.0000000000 0.0000000000 2.0000000000 90.0000000000 2.0000000000 0.0000000000 3.0000000000 90.0000000000 3.0000000000 0.0000000000 4.0000000000 90.0000000000 4.0000000000 0.0000000000 5.0000000000 90.000...
result:
ok correct
Test #30:
score: 0
Accepted
time: 3ms
memory: 3816kb
input:
90 81 121.0826164250
output:
3 0.0000000000 0.0000000000 44.9997873845 40.5001913539 90.0000000000 81.0000000000
result:
ok correct
Test #31:
score: 0
Accepted
time: 2ms
memory: 3868kb
input:
34 99 3366.0000000000
output:
100 0.0000000000 0.0000000000 34.0000000000 0.0000000000 0.0000000000 1.0000000000 34.0000000000 1.0000000000 0.0000000000 2.0000000000 34.0000000000 2.0000000000 0.0000000000 3.0000000000 34.0000000000 3.0000000000 0.0000000000 4.0000000000 34.0000000000 4.0000000000 0.0000000000 5.0000000000 34.00...
result:
ok correct
Test #32:
score: 0
Accepted
time: 3ms
memory: 3736kb
input:
34 99 104.6756896330
output:
3 0.0000000000 0.0000000000 16.9998996426 49.5002922172 34.0000000000 99.0000000000
result:
ok correct
Test #33:
score: 0
Accepted
time: 3ms
memory: 3648kb
input:
3 3 5.9999
output:
3 0.0000000000 0.0000000000 0.0000500001 2.9999499999 3.0000000000 3.0000000000
result:
ok correct
Test #34:
score: 0
Accepted
time: 3ms
memory: 3760kb
input:
3 3 6.0
output:
3 0.0000000000 0.0000000000 0.0000000007 2.9999999993 3.0000000000 3.0000000000
result:
ok correct
Test #35:
score: 0
Accepted
time: 3ms
memory: 3736kb
input:
3 3 6.0001
output:
4 0.0000000000 0.0000000000 3.0000000000 0.0000000000 2.9884528506 1.0000000000 3.0000000000 3.0000000000
result:
ok correct
Test #36:
score: 0
Accepted
time: 1ms
memory: 3784kb
input:
4 4 13.999998
output:
5 0.0000000000 0.0000000000 4.0000000000 0.0000000000 0.0000000000 1.0000000000 0.7280442934 3.4539667800 4.0000000000 4.0000000000
result:
ok correct
Test #37:
score: 0
Accepted
time: 3ms
memory: 3788kb
input:
4 4 14.0
output:
5 0.0000000000 0.0000000000 4.0000000000 0.0000000000 0.0000000000 1.0000000000 0.7280427520 3.4539679360 4.0000000000 4.0000000000
result:
ok correct
Test #38:
score: 0
Accepted
time: 0ms
memory: 3760kb
input:
4 4 14.000002
output:
5 0.0000000000 0.0000000000 4.0000000000 0.0000000000 0.0000000000 1.0000000000 0.7280412107 3.4539690920 4.0000000000 4.0000000000
result:
ok correct
Test #39:
score: 0
Accepted
time: 3ms
memory: 3724kb
input:
4 4 15.123104
output:
5 0.0000000000 0.0000000000 4.0000000000 0.0000000000 0.0000000000 1.0000000000 0.0000009290 3.9999993033 4.0000000000 4.0000000000
result:
ok correct
Test #40:
score: 0
Accepted
time: 3ms
memory: 3732kb
input:
4 4 15.123106
output:
5 0.0000000000 0.0000000000 4.0000000000 0.0000000000 0.0000000000 1.0000000000 0.0000000005 3.9999999997 4.0000000000 4.0000000000
result:
ok correct
Test #41:
score: 0
Accepted
time: 2ms
memory: 3708kb
input:
4 4 15.123108
output:
5 0.0000000000 0.0000000000 4.0000000000 0.0000000000 0.0000000000 1.0000000000 0.0000000005 3.9999999997 4.0000000000 4.0000000000
result:
ok correct
Test #42:
score: 0
Accepted
time: 2ms
memory: 3864kb
input:
4 4 14.593385
output:
5 0.0000000000 0.0000000000 4.0000000000 0.0000000000 0.0000000000 1.0000000000 0.3174850359 3.7618862231 4.0000000000 4.0000000000
result:
ok correct
Test #43:
score: 0
Accepted
time: 3ms
memory: 3864kb
input:
4 4 14.593387
output:
5 0.0000000000 0.0000000000 4.0000000000 0.0000000000 0.0000000000 1.0000000000 0.3174837711 3.7618871717 4.0000000000 4.0000000000
result:
ok correct
Test #44:
score: 0
Accepted
time: 0ms
memory: 3916kb
input:
4 4 14.593389
output:
5 0.0000000000 0.0000000000 4.0000000000 0.0000000000 0.0000000000 1.0000000000 0.3174825055 3.7618881209 4.0000000000 4.0000000000
result:
ok correct
Test #45:
score: 0
Accepted
time: 3ms
memory: 3856kb
input:
2 2 4.0
output:
3 0.0000000000 0.0000000000 0.0000000005 1.9999999995 2.0000000000 2.0000000000
result:
ok correct
Test #46:
score: 0
Accepted
time: 3ms
memory: 3716kb
input:
3 3 5.0
output:
3 0.0000000000 0.0000000000 0.5645856529 2.4354143471 3.0000000000 3.0000000000
result:
ok correct
Test #47:
score: 0
Accepted
time: 3ms
memory: 3732kb
input:
4 4 15.123
output:
5 0.0000000000 0.0000000000 4.0000000000 0.0000000000 0.0000000000 1.0000000000 0.0000603576 3.9999547318 4.0000000000 4.0000000000
result:
ok correct
Test #48:
score: 0
Accepted
time: 3ms
memory: 3784kb
input:
4 4 14.1
output:
5 0.0000000000 0.0000000000 4.0000000000 0.0000000000 0.0000000000 1.0000000000 0.6526609673 3.5105042745 4.0000000000 4.0000000000
result:
ok correct
Test #49:
score: 0
Accepted
time: 3ms
memory: 3860kb
input:
3 3 9.0
output:
4 0.0000000000 0.0000000000 3.0000000000 0.0000000000 0.4382623087 1.0000000000 3.0000000000 3.0000000000
result:
ok correct
Test #50:
score: 0
Accepted
time: 0ms
memory: 3724kb
input:
4 4 16.0
output:
6 0.0000000000 0.0000000000 4.0000000000 0.0000000000 0.0000000000 1.0000000000 4.0000000000 1.0000000000 2.8137137750 2.0000000000 4.0000000000 4.0000000000
result:
ok correct