QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#55082 | #2290. Kinking Cables | MIT01# | AC ✓ | 27ms | 8764kb | Python3 | 1.1kb | 2022-10-12 09:34:55 | 2022-10-12 09:34:57 |
Judging History
answer
import sys
def dist(A, B):
return ((A[0]-B[0])**2 + (A[1]-B[1])**2) ** 0.5
n, m = map(int, input().split())
l = float(input())
goal = (n, m)
at = (0, 0)
far = 0
ans = []
def get_pt(d, dest):
mid = (at[0] + goal[0]) / 2, (at[1] + goal[1]) / 2
vec = (dest[0] - mid[0]), (dest[1] - mid[1])
l = dist((0, 0), vec)
vec = vec[0]/l, vec[1]/l
return mid[0] + d * vec[0], mid[1] + d * vec[1]
def finish_off(dest):
lo, hi = 0, n + m
for i in range(100):
mid = (lo+hi) / 2
pt = get_pt(mid, dest)
if far + dist(at, pt) + dist(pt, goal) <= l:
lo = mid
else:
hi = mid
pt = get_pt(lo, dest)
ans.append(pt)
ans.append(goal)
def goto(dest):
if far + dist(at, dest) + dist(dest, goal) <= l:
ans.append(dest)
return dest, far + dist(at, dest)
else:
finish_off(dest)
output()
return None, None
def output():
print(len(ans))
for p in ans:
print(*p)
sys.exit(0)
for x in range(n+1):
if at is not None:
at, far = goto((x, 0))
if at is not None:
at, far = goto((x, m))
output()
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 16ms
memory: 8684kb
input:
79 78 1980.7712136406
output:
27 0 0 0 78 1 0 1 78 2 0 2 78 3 0 3 78 4 0 4 78 5 0 5 78 6 0 6 78 7 0 7 78 8 0 8 78 9 0 9 78 10 0 10 78 11 0 11 78 12 0 33.90212740422889 52.50200093239024 79 78
result:
ok correct
Test #2:
score: 0
Accepted
time: 14ms
memory: 8520kb
input:
33 65 1947.7601065763
output:
32 0 0 0 65 1 0 1 65 2 0 2 65 3 0 3 65 4 0 4 65 5 0 5 65 6 0 6 65 7 0 7 65 8 0 8 65 9 0 9 65 10 0 10 65 11 0 11 65 12 0 12 65 13 0 13 65 14 0 14 65 19.626368169816747 35.37810953389277 33 65
result:
ok correct
Test #3:
score: 0
Accepted
time: 11ms
memory: 8588kb
input:
51 51 555.0803652025
output:
12 0 0 0 51 1 0 1 51 2 0 2 51 3 0 3 51 4 0 4 51 10.256805209957871 11.915425142571173 51 51
result:
ok correct
Test #4:
score: 0
Accepted
time: 2ms
memory: 8612kb
input:
49 2 67.3588717350
output:
14 0 0 0 2 1 0 1 2 2 0 2 2 3 0 3 2 4 0 4 2 5 0 5 2 11.8451603896897 0.5566819418752096 49 2
result:
ok correct
Test #5:
score: 0
Accepted
time: 16ms
memory: 8580kb
input:
37 48 1713.3643608504
output:
38 0 0 0 48 1 0 1 48 2 0 2 48 3 0 3 48 4 0 4 48 5 0 5 48 6 0 6 48 7 0 7 48 8 0 8 48 9 0 9 48 10 0 10 48 11 0 11 48 12 0 12 48 13 0 13 48 14 0 14 48 15 0 15 48 16 0 16 48 17 0 17 48 24.544470398040872 34.90384212288466 37 48
result:
ok correct
Test #6:
score: 0
Accepted
time: 15ms
memory: 8536kb
input:
51 79 820.1218304546
output:
12 0 0 0 79 1 0 1 79 2 0 2 79 3 0 3 79 4 0 4 79 13.92110329770665 31.322984911947792 51 79
result:
ok correct
Test #7:
score: 0
Accepted
time: 11ms
memory: 8560kb
input:
6 8 37.5338494218
output:
6 0 0 0 8 1 0 1 8 2.3446294900525 1.8380239469466693 6 8
result:
ok correct
Test #8:
score: 0
Accepted
time: 13ms
memory: 8608kb
input:
5 5 7.1908428511
output:
3 0 0 2.037909517895036 2.962090482104964 5 5
result:
ok correct
Test #9:
score: 0
Accepted
time: 12ms
memory: 8544kb
input:
5 4 8.3927665498
output:
3 0 0 0.35126145236382866 3.7189908381089367 5 4
result:
ok correct
Test #10:
score: 0
Accepted
time: 9ms
memory: 8564kb
input:
4 2 6.4617533647
output:
4 0 0 0 2 1.5175265917800689 1.0350531835601378 4 2
result:
ok correct
Test #11:
score: 0
Accepted
time: 20ms
memory: 8584kb
input:
91 87 4830.8473359767
output:
57 0 0 0 87 1 0 1 87 2 0 2 87 3 0 3 87 4 0 4 87 5 0 5 87 6 0 6 87 7 0 7 87 8 0 8 87 9 0 9 87 10 0 10 87 11 0 11 87 12 0 12 87 13 0 13 87 14 0 14 87 15 0 15 87 16 0 16 87 17 0 17 87 18 0 18 87 19 0 19 87 20 0 20 87 21 0 21 87 22 0 22 87 23 0 23 87 24 0 24 87 25 0 25 87 26 0 26 87 27 0 35.459062621623...
result:
ok correct
Test #12:
score: 0
Accepted
time: 10ms
memory: 8540kb
input:
90 90 5088.9280941138
output:
58 0 0 0 90 1 0 1 90 2 0 2 90 3 0 3 90 4 0 4 90 5 0 5 90 6 0 6 90 7 0 7 90 8 0 8 90 9 0 9 90 10 0 10 90 11 0 11 90 12 0 12 90 13 0 13 90 14 0 14 90 15 0 15 90 16 0 16 90 17 0 17 90 18 0 18 90 19 0 19 90 20 0 20 90 21 0 21 90 22 0 22 90 23 0 23 90 24 0 24 90 25 0 25 90 26 0 26 90 27 0 27 90 38.441965...
result:
ok correct
Test #13:
score: 0
Accepted
time: 15ms
memory: 8552kb
input:
90 92 7004.0153432299
output:
78 0 0 0 92 1 0 1 92 2 0 2 92 3 0 3 92 4 0 4 92 5 0 5 92 6 0 6 92 7 0 7 92 8 0 8 92 9 0 9 92 10 0 10 92 11 0 11 92 12 0 12 92 13 0 13 92 14 0 14 92 15 0 15 92 16 0 16 92 17 0 17 92 18 0 18 92 19 0 19 92 20 0 20 92 21 0 21 92 22 0 22 92 23 0 23 92 24 0 24 92 25 0 25 92 26 0 26 92 27 0 27 92 28 0 28 9...
result:
ok correct
Test #14:
score: 0
Accepted
time: 25ms
memory: 8564kb
input:
91 83 1879.3819547895
output:
24 0 0 0 83 1 0 1 83 2 0 2 83 3 0 3 83 4 0 4 83 5 0 5 83 6 0 6 83 7 0 7 83 8 0 8 83 9 0 9 83 10 0 10 83 26.133286908961836 31.79905856819829 91 83
result:
ok correct
Test #15:
score: 0
Accepted
time: 0ms
memory: 8636kb
input:
3 81 199.2077743610
output:
4 0 0 0 81 1.1352856487182215 21.916275092351874 3 81
result:
ok correct
Test #16:
score: 0
Accepted
time: 10ms
memory: 8520kb
input:
4 89 288.5915130114
output:
6 0 0 0 89 1 0 1 89 2.4399548358776775 78.31196078622663 4 89
result:
ok correct
Test #17:
score: 0
Accepted
time: 9ms
memory: 8544kb
input:
95 3 175.9210001082
output:
34 0 0 0 3 1 0 1 3 2 0 2 3 3 0 3 3 4 0 4 3 5 0 5 3 6 0 6 3 7 0 7 3 8 0 8 3 9 0 9 3 10 0 10 3 11 0 11 3 12 0 12 3 13 0 13 3 14 0 14 3 15 0 15 3 22.038119356048774 0.4644707196960596 95 3
result:
ok correct
Test #18:
score: 0
Accepted
time: 8ms
memory: 8552kb
input:
84 4 310.3037172015
output:
66 0 0 0 4 1 0 1 4 2 0 2 4 3 0 3 4 4 0 4 4 5 0 5 4 6 0 6 4 7 0 7 4 8 0 8 4 9 0 9 4 10 0 10 4 11 0 11 4 12 0 12 4 13 0 13 4 14 0 14 4 15 0 15 4 16 0 16 4 17 0 17 4 18 0 18 4 19 0 19 4 20 0 20 4 21 0 21 4 22 0 22 4 23 0 23 4 24 0 24 4 25 0 25 4 26 0 26 4 27 0 27 4 28 0 28 4 29 0 29 4 30 0 30 4 31 0 31...
result:
ok correct
Test #19:
score: 0
Accepted
time: 25ms
memory: 8568kb
input:
2 2 2.8284271248
output:
3 0 0 0.9999938315581772 1.0000061684418229 2 2
result:
ok correct
Test #20:
score: 0
Accepted
time: 25ms
memory: 8596kb
input:
100 100 10000.0000000000
output:
102 0 0 0 100 1 0 1 100 2 0 2 100 3 0 3 100 4 0 4 100 5 0 5 100 6 0 6 100 7 0 7 100 8 0 8 100 9 0 9 100 10 0 10 100 11 0 11 100 12 0 12 100 13 0 13 100 14 0 14 100 15 0 15 100 16 0 16 100 17 0 17 100 18 0 18 100 19 0 19 100 20 0 20 100 21 0 21 100 22 0 22 100 23 0 23 100 24 0 24 100 25 0 25 100 26 0...
result:
ok correct
Test #21:
score: 0
Accepted
time: 6ms
memory: 8572kb
input:
100 100 9999.2500000000
output:
102 0 0 0 100 1 0 1 100 2 0 2 100 3 0 3 100 4 0 4 100 5 0 5 100 6 0 6 100 7 0 7 100 8 0 8 100 9 0 9 100 10 0 10 100 11 0 11 100 12 0 12 100 13 0 13 100 14 0 14 100 15 0 15 100 16 0 16 100 17 0 17 100 18 0 18 100 19 0 19 100 20 0 20 100 21 0 21 100 22 0 22 100 23 0 23 100 24 0 24 100 25 0 25 100 26 0...
result:
ok correct
Test #22:
score: 0
Accepted
time: 5ms
memory: 8544kb
input:
100 100 2723.8981892905
output:
28 0 0 0 100 1 0 1 100 2 0 2 100 3 0 3 100 4 0 4 100 5 0 5 100 6 0 6 100 7 0 7 100 8 0 8 100 9 0 9 100 10 0 10 100 11 0 11 100 12 0 12 100 14.849540756695866 4.301257573711325 100 100
result:
ok correct
Test #23:
score: 0
Accepted
time: 8ms
memory: 8528kb
input:
100 100 8994.4904261819
output:
92 0 0 0 100 1 0 1 100 2 0 2 100 3 0 3 100 4 0 4 100 5 0 5 100 6 0 6 100 7 0 7 100 8 0 8 100 9 0 9 100 10 0 10 100 11 0 11 100 12 0 12 100 13 0 13 100 14 0 14 100 15 0 15 100 16 0 16 100 17 0 17 100 18 0 18 100 19 0 19 100 20 0 20 100 21 0 21 100 22 0 22 100 23 0 23 100 24 0 24 100 25 0 25 100 26 0 ...
result:
ok correct
Test #24:
score: 0
Accepted
time: 12ms
memory: 8636kb
input:
100 100 881.4998747190
output:
10 0 0 0 100 1 0 1 100 2 0 2 100 3 0 3 100 17.693063995574462 28.82750314857782 100 100
result:
ok correct
Test #25:
score: 0
Accepted
time: 5ms
memory: 8524kb
input:
88 94 8266.2500000000
output:
90 0 0 0 94 1 0 1 94 2 0 2 94 3 0 3 94 4 0 4 94 5 0 5 94 6 0 6 94 7 0 7 94 8 0 8 94 9 0 9 94 10 0 10 94 11 0 11 94 12 0 12 94 13 0 13 94 14 0 14 94 15 0 15 94 16 0 16 94 17 0 17 94 18 0 18 94 19 0 19 94 20 0 20 94 21 0 21 94 22 0 22 94 23 0 23 94 24 0 24 94 25 0 25 94 26 0 26 94 27 0 27 94 28 0 28 9...
result:
ok correct
Test #26:
score: 0
Accepted
time: 27ms
memory: 8584kb
input:
75 37 2772.0000000000
output:
76 0 0 0 37 1 0 1 37 2 0 2 37 3 0 3 37 4 0 4 37 5 0 5 37 6 0 6 37 7 0 7 37 8 0 8 37 9 0 9 37 10 0 10 37 11 0 11 37 12 0 12 37 13 0 13 37 14 0 14 37 15 0 15 37 16 0 16 37 17 0 17 37 18 0 18 37 19 0 19 37 20 0 20 37 21 0 21 37 22 0 22 37 23 0 23 37 24 0 24 37 25 0 25 37 26 0 26 37 27 0 27 37 28 0 28 3...
result:
ok correct
Test #27:
score: 0
Accepted
time: 23ms
memory: 8576kb
input:
48 39 62.0000000000
output:
3 0 0 22.272090535957997 20.90392643953413 48 39
result:
ok correct
Test #28:
score: 0
Accepted
time: 11ms
memory: 8536kb
input:
98 94 135.9000000000
output:
3 0 0 47.06150960271016 48.859368340257596 98 94
result:
ok correct
Test #29:
score: 0
Accepted
time: 2ms
memory: 8588kb
input:
90 81 7290.0000000000
output:
92 0 0 0 81 1 0 1 81 2 0 2 81 3 0 3 81 4 0 4 81 5 0 5 81 6 0 6 81 7 0 7 81 8 0 8 81 9 0 9 81 10 0 10 81 11 0 11 81 12 0 12 81 13 0 13 81 14 0 14 81 15 0 15 81 16 0 16 81 17 0 17 81 18 0 18 81 19 0 19 81 20 0 20 81 21 0 21 81 22 0 22 81 23 0 23 81 24 0 24 81 25 0 25 81 26 0 26 81 27 0 27 81 28 0 28 8...
result:
ok correct
Test #30:
score: 0
Accepted
time: 25ms
memory: 8588kb
input:
90 81 121.0826164250
output:
3 0 0 44.99978738380184 40.50019135457835 90 81
result:
ok correct
Test #31:
score: 0
Accepted
time: 15ms
memory: 8608kb
input:
34 99 3366.0000000000
output:
36 0 0 0 99 1 0 1 99 2 0 2 99 3 0 3 99 4 0 4 99 5 0 5 99 6 0 6 99 7 0 7 99 8 0 8 99 9 0 9 99 10 0 10 99 11 0 11 99 12 0 12 99 13 0 13 99 14 0 14 99 15 0 15 99 16 0 16 99 21.082339672192795 50.51895344338582 34 99
result:
ok correct
Test #32:
score: 0
Accepted
time: 13ms
memory: 8548kb
input:
34 99 104.6756896330
output:
3 0 0 16.999899641984584 49.50029221892725 34 99
result:
ok correct
Test #33:
score: 0
Accepted
time: 15ms
memory: 8564kb
input:
3 3 5.9999
output:
3 0 0 5.000041668057342e-05 2.999949999583319 3 3
result:
ok correct
Test #34:
score: 0
Accepted
time: 10ms
memory: 8608kb
input:
3 3 6.0
output:
4 0 0 0 3 1.4999999944728284 2.9999999668369695 3 3
result:
ok correct
Test #35:
score: 0
Accepted
time: 8ms
memory: 8636kb
input:
3 3 6.0001
output:
4 0 0 0 3 1.4979587434273616 2.9877524605641685 3 3
result:
ok correct
Test #36:
score: 0
Accepted
time: 10ms
memory: 8548kb
input:
4 4 13.999998
output:
5 0 0 0 4 1 0 1.5460332198415194 3.271955706877974 4 4
result:
ok correct
Test #37:
score: 0
Accepted
time: 13ms
memory: 8532kb
input:
4 4 14.0
output:
5 0 0 0 4 1 0 1.546032063773394 3.271957248302141 4 4
result:
ok correct
Test #38:
score: 0
Accepted
time: 8ms
memory: 8584kb
input:
4 4 14.000002
output:
5 0 0 0 4 1 0 1.5460309077063437 3.2719587897248754 4 4
result:
ok correct
Test #39:
score: 0
Accepted
time: 18ms
memory: 8544kb
input:
4 4 15.123104
output:
5 0 0 0 4 1 0 1.000000696693371 3.9999990710755053 4 4
result:
ok correct
Test #40:
score: 0
Accepted
time: 24ms
memory: 8592kb
input:
4 4 15.123106
output:
6 0 0 0 4 1 0 1 4 2.4999063272366353 3.9992506178930807 4 4
result:
ok correct
Test #41:
score: 0
Accepted
time: 9ms
memory: 8556kb
input:
4 4 15.123108
output:
6 0 0 0 4 1 0 1 4 2.4997640983112994 3.9981127864903936 4 4
result:
ok correct
Test #42:
score: 0
Accepted
time: 13ms
memory: 8608kb
input:
4 4 14.593385
output:
5 0 0 0 4 1 0 1.2381137771801052 3.6825149637598598 4 4
result:
ok correct
Test #43:
score: 0
Accepted
time: 11ms
memory: 8576kb
input:
4 4 14.593387
output:
5 0 0 0 4 1 0 1.238112828062374 3.682516229250168 4 4
result:
ok correct
Test #44:
score: 0
Accepted
time: 18ms
memory: 8520kb
input:
4 4 14.593389
output:
5 0 0 0 4 1 0 1.2381118789450973 3.6825174947398702 4 4
result:
ok correct
Test #45:
score: 0
Accepted
time: 18ms
memory: 8764kb
input:
2 2 4.0
output:
4 0 0 0 2 1.0 1.9999999721224802 2 2
result:
ok correct
Test #46:
score: 0
Accepted
time: 24ms
memory: 8588kb
input:
3 3 5.0
output:
3 0 0 0.5645856533065142 2.4354143466934857 3 3
result:
ok correct
Test #47:
score: 0
Accepted
time: 0ms
memory: 8520kb
input:
4 4 15.123
output:
5 0 0 0 4 1 0 1.0000452684918617 3.999939642010851 4 4
result:
ok correct
Test #48:
score: 0
Accepted
time: 19ms
memory: 8612kb
input:
4 4 14.1
output:
5 0 0 0 4 1 0 1.4894957252179357 3.3473390330427524 4 4
result:
ok correct
Test #49:
score: 0
Accepted
time: 22ms
memory: 8536kb
input:
3 3 9.0
output:
4 0 0 0 3 1.0714285714285714 0.4285714285714284 3 3
result:
ok correct
Test #50:
score: 0
Accepted
time: 13ms
memory: 8496kb
input:
4 4 16.0
output:
6 0 0 0 4 1 0 1 4 2.3469995141931075 2.7759961135448603 4 4
result:
ok correct