QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#55082#2290. Kinking CablesMIT01#AC ✓27ms8764kbPython31.1kb2022-10-12 09:34:552022-10-12 09:34:57

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-10-12 09:34:57]
  • 评测
  • 测评结果:AC
  • 用时:27ms
  • 内存:8764kb
  • [2022-10-12 09:34:55]
  • 提交

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