QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#56583#2290. Kinking CableszghtyarecrenjAC ✓3ms3940kbC++171.6kb2022-10-20 11:20:502022-10-20 11:20:51

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-20 11:20:51]
  • 评测
  • 测评结果:AC
  • 用时:3ms
  • 内存:3940kb
  • [2022-10-20 11:20:50]
  • 提交

answer

#include <bits/stdc++.h>

typedef double db;
typedef long double ld;
const ld eps = 1e-12;

inline ld dist(ld x1, ld y1, ld x2, ld y2) {
    return sqrt((x2 - x1) * (x2 - x1) + (y2 - y1) * (y2 - y1));
}

inline ld dist(std::pair<ld, ld> x, std::pair<ld, ld> y) {
    return dist(x.first, x.second, y.first, y.second);
}

int n, m;
ld t;
std::vector<std::pair<ld, ld>> v;

int main() {
    scanf("%d%d%Lf", &n, &m, &t);
    std::pair<ld, ld> des(n, m), add(-1, -1);
    for (int i = 0; i <= n; ++i) {
        if (i & 1) v.emplace_back(i, m), v.emplace_back(i, 0);
        else v.emplace_back(i, 0), v.emplace_back(i, m);
    }
    int fin = 0;
    for (int i = 1; i < v.size(); ++i) {
        if (dist(v[i], v[i - 1]) + dist(v[i], des) > t + eps) {
            fin = i;
            ld l = 0, r = 1;
            for (int j = 0; j < 256; ++j) {
                ld mid = (l + r) / 2.0;
                std::pair<ld, ld> cur(v[i - 1].first * (1 - mid) + v[i].first * mid, v[i - 1].second * (1 - mid) + v[i].second * mid);
                if (dist(v[i - 1], cur) + dist(cur, des) > t) r = mid; else l = mid;
            }
            std::pair<ld, ld> cur(v[i - 1].first * (1 - l) + v[i].first * l, v[i - 1].second * (1 - l) + v[i].second * l);
            if (dist(cur, v[i - 1]) > eps) add = cur;
            break;
        }
        t -= dist(v[i], v[i - 1]);
    }
    printf("%d\n", fin + (add.first != -1) + 1);
    for (int i = 0; i < fin; ++i) printf("%.10Lf %.10Lf\n", v[i].first, v[i].second);
    if (add.first != -1) printf("%.10Lf %.10Lf\n", add.first, add.second);
    printf("%d %d\n", n, m);
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 2ms
memory: 3768kb

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: 2ms
memory: 3788kb

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: 2ms
memory: 3776kb

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: 3788kb

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: 2ms
memory: 3780kb

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: 2ms
memory: 3784kb

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: 2ms
memory: 3788kb

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.1602695483
6 8

result:

ok correct

Test #8:

score: 0
Accepted
time: 0ms
memory: 3784kb

input:

5 5
7.1908428511

output:

3
0.0000000000 0.0000000000
0.0000000000 0.3898547329
5 5

result:

ok correct

Test #9:

score: 0
Accepted
time: 2ms
memory: 3652kb

input:

5 4
8.3927665498

output:

3
0.0000000000 0.0000000000
0.0000000000 3.3507961356
5 4

result:

ok correct

Test #10:

score: 0
Accepted
time: 2ms
memory: 3780kb

input:

4 2
6.4617533647

output:

5
0.0000000000 0.0000000000
0.0000000000 2.0000000000
1.0000000000 2.0000000000
1.0000000000 1.5690426146
4 2

result:

ok correct

Test #11:

score: 0
Accepted
time: 2ms
memory: 3792kb

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: 2ms
memory: 3756kb

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: 2ms
memory: 3776kb

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: 2ms
memory: 3720kb

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: 2ms
memory: 3784kb

input:

3 81
199.2077743610

output:

5
0.0000000000 0.0000000000
0.0000000000 81.0000000000
1.0000000000 81.0000000000
1.0000000000 22.4131765340
3 81

result:

ok correct

Test #16:

score: 0
Accepted
time: 1ms
memory: 3856kb

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.7311374862
4 89

result:

ok correct

Test #17:

score: 0
Accepted
time: 2ms
memory: 3660kb

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: 2ms
memory: 3776kb

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: 3816kb

input:

2 2
2.8284271248

output:

3
0.0000000000 0.0000000000
0.0000000000 0.0000000002
2 2

result:

ok correct

Test #20:

score: 0
Accepted
time: 2ms
memory: 3792kb

input:

100 100
10000.0000000000

output:

200
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: 2ms
memory: 3940kb

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: 2ms
memory: 3664kb

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: 3800kb

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: 2ms
memory: 3828kb

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: 2ms
memory: 3780kb

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: 3800kb

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: 1ms
memory: 3856kb

input:

48 39
62.0000000000

output:

3
0.0000000000 0.0000000000
0.0000000000 0.4130434783
48 39

result:

ok correct

Test #28:

score: 0
Accepted
time: 2ms
memory: 3768kb

input:

98 94
135.9000000000

output:

3
0.0000000000 0.0000000000
0.0000000000 0.3437947494
98 94

result:

ok correct

Test #29:

score: 0
Accepted
time: 2ms
memory: 3888kb

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: 3888kb

input:

90 81
121.0826164250

output:

3
0.0000000000 0.0000000000
0.0000000000 0.0000000040
90 81

result:

ok correct

Test #31:

score: 0
Accepted
time: 0ms
memory: 3776kb

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: 3ms
memory: 3864kb

input:

34 99
104.6756896330

output:

3
0.0000000000 0.0000000000
0.0000000000 0.0000000127
34 99

result:

ok correct

Test #33:

score: 0
Accepted
time: 2ms
memory: 3780kb

input:

3 3
5.9999

output:

3
0.0000000000 0.0000000000
0.0000000000 2.9998999983
3 3

result:

ok correct

Test #34:

score: 0
Accepted
time: 3ms
memory: 3784kb

input:

3 3
6.0

output:

4
0.0000000000 0.0000000000
0.0000000000 3.0000000000
1.0000000000 3.0000000000
3 3

result:

ok correct

Test #35:

score: 0
Accepted
time: 0ms
memory: 3652kb

input:

3 3
6.0001

output:

5
0.0000000000 0.0000000000
0.0000000000 3.0000000000
1.0000000000 3.0000000000
1.0000000000 2.9999000025
3 3

result:

ok correct

Test #36:

score: 0
Accepted
time: 0ms
memory: 3768kb

input:

4 4
13.999998

output:

5
0.0000000000 0.0000000000
0.0000000000 4.0000000000
1.0000000000 4.0000000000
1.0000000000 0.0000011111
4 4

result:

ok correct

Test #37:

score: 0
Accepted
time: 2ms
memory: 3764kb

input:

4 4
14.0

output:

5
0.0000000000 0.0000000000
0.0000000000 4.0000000000
1.0000000000 4.0000000000
1.0000000000 0.0000000000
4 4

result:

ok correct

Test #38:

score: 0
Accepted
time: 2ms
memory: 3784kb

input:

4 4
14.000002

output:

6
0.0000000000 0.0000000000
0.0000000000 4.0000000000
1.0000000000 4.0000000000
1.0000000000 0.0000000000
1.0000050000 0.0000000000
4 4

result:

ok correct

Test #39:

score: 0
Accepted
time: 2ms
memory: 3784kb

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.7807730160
4 4

result:

ok correct

Test #40:

score: 0
Accepted
time: 2ms
memory: 3796kb

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.7807771872
4 4

result:

ok correct

Test #41:

score: 0
Accepted
time: 2ms
memory: 3928kb

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.7807813584
4 4

result:

ok correct

Test #42:

score: 0
Accepted
time: 2ms
memory: 3776kb

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.9261994811
4 4

result:

ok correct

Test #43:

score: 0
Accepted
time: 2ms
memory: 3720kb

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.9262118413
4 4

result:

ok correct

Test #44:

score: 0
Accepted
time: 2ms
memory: 3928kb

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.9262242014
4 4

result:

ok correct

Test #45:

score: 0
Accepted
time: 2ms
memory: 3792kb

input:

2 2
4.0

output:

4
0.0000000000 0.0000000000
0.0000000000 2.0000000000
1.0000000000 2.0000000000
2 2

result:

ok correct

Test #46:

score: 0
Accepted
time: 2ms
memory: 3756kb

input:

3 3
5.0

output:

3
0.0000000000 0.0000000000
0.0000000000 1.7500000000
3 3

result:

ok correct

Test #47:

score: 0
Accepted
time: 2ms
memory: 3748kb

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.7805560997
4 4

result:

ok correct

Test #48:

score: 0
Accepted
time: 0ms
memory: 3764kb

input:

4 4
14.1

output:

6
0.0000000000 0.0000000000
0.0000000000 4.0000000000
1.0000000000 4.0000000000
1.0000000000 0.0000000000
1.2404761905 0.0000000000
4 4

result:

ok correct

Test #49:

score: 0
Accepted
time: 1ms
memory: 3772kb

input:

3 3
9.0

output:

5
0.0000000000 0.0000000000
0.0000000000 3.0000000000
1.0000000000 3.0000000000
1.0000000000 0.9000000000
3 3

result:

ok correct

Test #50:

score: 0
Accepted
time: 0ms
memory: 3644kb

input:

4 4
16.0

output:

8
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
4 4

result:

ok correct