QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#202447#2290. Kinking CablesMaGnsi0AC ✓1ms4064kbC++171.9kb2023-10-06 03:11:072023-10-06 03:11:08

Judging History

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

  • [2023-10-06 03:11:08]
  • 评测
  • 测评结果:AC
  • 用时:1ms
  • 内存:4064kb
  • [2023-10-06 03:11:07]
  • 提交

answer

/**
 *    author:  MaGnsi0
 *    created: 05.10.2023 21:43:55
**/
#include <bits/stdc++.h>

using namespace std;

const long double eps = 1e-6;

long double dist(long double x1, long double y1, long double x2, long double y2) {
    long double dx = x1 - x2;
    long double dy = y1 - y2;
    return sqrt(dx * dx + dy * dy);
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int n; cin >> n;
    int m; cin >> m;
    long double L; cin >> L;
    int x = 0, y = 0;
    vector<double> X(1, 0), Y(1, 0);
    while (true) {
        int x_ = x, y_ = y;
        if (x % 2 == 0 && y == 0) { y_ = m; }
        if (x % 2 == 0 && y == m) { x_++; }
        if (x % 2 == 1 && y == 0) { x_++; }
        if (x % 2 == 1 && y == m) { y_ = 0; }
        long double D = dist(x, y, x_, y_) + dist(x_, y_, n, m);
        if (L > D) {
            L -= dist(x, y, x_, y_);
            x = x_, y = y_;
            X.push_back(x);
            Y.push_back(y);
            continue;
        }
        long double low = 0, high = 1;
        for (int _ = 0; _ <= 100; _++) {
            long double mid = (low + high) / 2;
            long double x_mid = x_ * mid + x * (1 - mid);
            long double y_mid = y_ * mid + y * (1 - mid);
            D = dist(x, y, x_mid, y_mid) + dist(x_mid, y_mid, n, m);
            if (L > D) {
                low = mid;
            } else {
                high = mid;
            }
        }
        long double x_mid = x_ * low + x * (1 - low);
        long double y_mid = y_ * low + y * (1 - low);
        if (low > 0 && low < 1) {
            X.push_back(x_mid);
            Y.push_back(y_mid);
        }
        X.push_back(n);
        Y.push_back(m);
        break;
    }
    int k = (int)X.size();
    cout << k << "\n";
    cout << fixed << setprecision(6);
    for (int i = 0; i < k; ++i) {
        cout << X[i] << " " << Y[i] << "\n";
    }
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3816kb

input:

79 78
1980.7712136406

output:

49
0.000000 0.000000
0.000000 78.000000
1.000000 78.000000
1.000000 0.000000
2.000000 0.000000
2.000000 78.000000
3.000000 78.000000
3.000000 0.000000
4.000000 0.000000
4.000000 78.000000
5.000000 78.000000
5.000000 0.000000
6.000000 0.000000
6.000000 78.000000
7.000000 78.000000
7.000000 0.000000
8...

result:

ok correct

Test #2:

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

input:

33 65
1947.7601065763

output:

61
0.000000 0.000000
0.000000 65.000000
1.000000 65.000000
1.000000 0.000000
2.000000 0.000000
2.000000 65.000000
3.000000 65.000000
3.000000 0.000000
4.000000 0.000000
4.000000 65.000000
5.000000 65.000000
5.000000 0.000000
6.000000 0.000000
6.000000 65.000000
7.000000 65.000000
7.000000 0.000000
8...

result:

ok correct

Test #3:

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

input:

51 51
555.0803652025

output:

21
0.000000 0.000000
0.000000 51.000000
1.000000 51.000000
1.000000 0.000000
2.000000 0.000000
2.000000 51.000000
3.000000 51.000000
3.000000 0.000000
4.000000 0.000000
4.000000 51.000000
5.000000 51.000000
5.000000 0.000000
6.000000 0.000000
6.000000 51.000000
7.000000 51.000000
7.000000 0.000000
8...

result:

ok correct

Test #4:

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

input:

49 2
67.3588717350

output:

21
0.000000 0.000000
0.000000 2.000000
1.000000 2.000000
1.000000 0.000000
2.000000 0.000000
2.000000 2.000000
3.000000 2.000000
3.000000 0.000000
4.000000 0.000000
4.000000 2.000000
5.000000 2.000000
5.000000 0.000000
6.000000 0.000000
6.000000 2.000000
7.000000 2.000000
7.000000 0.000000
8.000000 ...

result:

ok correct

Test #5:

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

input:

37 48
1713.3643608504

output:

70
0.000000 0.000000
0.000000 48.000000
1.000000 48.000000
1.000000 0.000000
2.000000 0.000000
2.000000 48.000000
3.000000 48.000000
3.000000 0.000000
4.000000 0.000000
4.000000 48.000000
5.000000 48.000000
5.000000 0.000000
6.000000 0.000000
6.000000 48.000000
7.000000 48.000000
7.000000 0.000000
8...

result:

ok correct

Test #6:

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

input:

51 79
820.1218304546

output:

21
0.000000 0.000000
0.000000 79.000000
1.000000 79.000000
1.000000 0.000000
2.000000 0.000000
2.000000 79.000000
3.000000 79.000000
3.000000 0.000000
4.000000 0.000000
4.000000 79.000000
5.000000 79.000000
5.000000 0.000000
6.000000 0.000000
6.000000 79.000000
7.000000 79.000000
7.000000 0.000000
8...

result:

ok correct

Test #7:

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

input:

6 8
37.5338494218

output:

9
0.000000 0.000000
0.000000 8.000000
1.000000 8.000000
1.000000 0.000000
2.000000 0.000000
2.000000 8.000000
3.000000 8.000000
3.000000 3.160270
6.000000 8.000000

result:

ok correct

Test #8:

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

input:

5 5
7.1908428511

output:

3
0.000000 0.000000
0.000000 0.389855
5.000000 5.000000

result:

ok correct

Test #9:

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

input:

5 4
8.3927665498

output:

3
0.000000 0.000000
0.000000 3.350796
5.000000 4.000000

result:

ok correct

Test #10:

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

input:

4 2
6.4617533647

output:

5
0.000000 0.000000
0.000000 2.000000
1.000000 2.000000
1.000000 1.569043
4.000000 2.000000

result:

ok correct

Test #11:

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

input:

91 87
4830.8473359767

output:

109
0.000000 0.000000
0.000000 87.000000
1.000000 87.000000
1.000000 0.000000
2.000000 0.000000
2.000000 87.000000
3.000000 87.000000
3.000000 0.000000
4.000000 0.000000
4.000000 87.000000
5.000000 87.000000
5.000000 0.000000
6.000000 0.000000
6.000000 87.000000
7.000000 87.000000
7.000000 0.000000
...

result:

ok correct

Test #12:

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

input:

90 90
5088.9280941138

output:

113
0.000000 0.000000
0.000000 90.000000
1.000000 90.000000
1.000000 0.000000
2.000000 0.000000
2.000000 90.000000
3.000000 90.000000
3.000000 0.000000
4.000000 0.000000
4.000000 90.000000
5.000000 90.000000
5.000000 0.000000
6.000000 0.000000
6.000000 90.000000
7.000000 90.000000
7.000000 0.000000
...

result:

ok correct

Test #13:

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

input:

90 92
7004.0153432299

output:

153
0.000000 0.000000
0.000000 92.000000
1.000000 92.000000
1.000000 0.000000
2.000000 0.000000
2.000000 92.000000
3.000000 92.000000
3.000000 0.000000
4.000000 0.000000
4.000000 92.000000
5.000000 92.000000
5.000000 0.000000
6.000000 0.000000
6.000000 92.000000
7.000000 92.000000
7.000000 0.000000
...

result:

ok correct

Test #14:

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

input:

91 83
1879.3819547895

output:

45
0.000000 0.000000
0.000000 83.000000
1.000000 83.000000
1.000000 0.000000
2.000000 0.000000
2.000000 83.000000
3.000000 83.000000
3.000000 0.000000
4.000000 0.000000
4.000000 83.000000
5.000000 83.000000
5.000000 0.000000
6.000000 0.000000
6.000000 83.000000
7.000000 83.000000
7.000000 0.000000
8...

result:

ok correct

Test #15:

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

input:

3 81
199.2077743610

output:

5
0.000000 0.000000
0.000000 81.000000
1.000000 81.000000
1.000000 22.413177
3.000000 81.000000

result:

ok correct

Test #16:

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

input:

4 89
288.5915130114

output:

9
0.000000 0.000000
0.000000 89.000000
1.000000 89.000000
1.000000 0.000000
2.000000 0.000000
2.000000 89.000000
3.000000 89.000000
3.000000 79.731137
4.000000 89.000000

result:

ok correct

Test #17:

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

input:

95 3
175.9210001082

output:

55
0.000000 0.000000
0.000000 3.000000
1.000000 3.000000
1.000000 0.000000
2.000000 0.000000
2.000000 3.000000
3.000000 3.000000
3.000000 0.000000
4.000000 0.000000
4.000000 3.000000
5.000000 3.000000
5.000000 0.000000
6.000000 0.000000
6.000000 3.000000
7.000000 3.000000
7.000000 0.000000
8.000000 ...

result:

ok correct

Test #18:

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

input:

84 4
310.3037172015

output:

115
0.000000 0.000000
0.000000 4.000000
1.000000 4.000000
1.000000 0.000000
2.000000 0.000000
2.000000 4.000000
3.000000 4.000000
3.000000 0.000000
4.000000 0.000000
4.000000 4.000000
5.000000 4.000000
5.000000 0.000000
6.000000 0.000000
6.000000 4.000000
7.000000 4.000000
7.000000 0.000000
8.000000...

result:

ok correct

Test #19:

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

input:

2 2
2.8284271248

output:

3
0.000000 0.000000
0.000000 0.000000
2.000000 2.000000

result:

ok correct

Test #20:

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

input:

100 100
10000.0000000000

output:

199
0.000000 0.000000
0.000000 100.000000
1.000000 100.000000
1.000000 0.000000
2.000000 0.000000
2.000000 100.000000
3.000000 100.000000
3.000000 0.000000
4.000000 0.000000
4.000000 100.000000
5.000000 100.000000
5.000000 0.000000
6.000000 0.000000
6.000000 100.000000
7.000000 100.000000
7.000000 0...

result:

ok correct

Test #21:

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

input:

100 100
9999.2500000000

output:

199
0.000000 0.000000
0.000000 100.000000
1.000000 100.000000
1.000000 0.000000
2.000000 0.000000
2.000000 100.000000
3.000000 100.000000
3.000000 0.000000
4.000000 0.000000
4.000000 100.000000
5.000000 100.000000
5.000000 0.000000
6.000000 0.000000
6.000000 100.000000
7.000000 100.000000
7.000000 0...

result:

ok correct

Test #22:

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

input:

100 100
2723.8981892905

output:

53
0.000000 0.000000
0.000000 100.000000
1.000000 100.000000
1.000000 0.000000
2.000000 0.000000
2.000000 100.000000
3.000000 100.000000
3.000000 0.000000
4.000000 0.000000
4.000000 100.000000
5.000000 100.000000
5.000000 0.000000
6.000000 0.000000
6.000000 100.000000
7.000000 100.000000
7.000000 0....

result:

ok correct

Test #23:

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

input:

100 100
8994.4904261819

output:

179
0.000000 0.000000
0.000000 100.000000
1.000000 100.000000
1.000000 0.000000
2.000000 0.000000
2.000000 100.000000
3.000000 100.000000
3.000000 0.000000
4.000000 0.000000
4.000000 100.000000
5.000000 100.000000
5.000000 0.000000
6.000000 0.000000
6.000000 100.000000
7.000000 100.000000
7.000000 0...

result:

ok correct

Test #24:

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

input:

100 100
881.4998747190

output:

17
0.000000 0.000000
0.000000 100.000000
1.000000 100.000000
1.000000 0.000000
2.000000 0.000000
2.000000 100.000000
3.000000 100.000000
3.000000 0.000000
4.000000 0.000000
4.000000 100.000000
5.000000 100.000000
5.000000 0.000000
6.000000 0.000000
6.000000 100.000000
7.000000 100.000000
7.000000 37...

result:

ok correct

Test #25:

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

input:

88 94
8266.2500000000

output:

177
0.000000 0.000000
0.000000 94.000000
1.000000 94.000000
1.000000 0.000000
2.000000 0.000000
2.000000 94.000000
3.000000 94.000000
3.000000 0.000000
4.000000 0.000000
4.000000 94.000000
5.000000 94.000000
5.000000 0.000000
6.000000 0.000000
6.000000 94.000000
7.000000 94.000000
7.000000 0.000000
...

result:

ok correct

Test #26:

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

input:

75 37
2772.0000000000

output:

145
0.000000 0.000000
0.000000 37.000000
1.000000 37.000000
1.000000 0.000000
2.000000 0.000000
2.000000 37.000000
3.000000 37.000000
3.000000 0.000000
4.000000 0.000000
4.000000 37.000000
5.000000 37.000000
5.000000 0.000000
6.000000 0.000000
6.000000 37.000000
7.000000 37.000000
7.000000 0.000000
...

result:

ok correct

Test #27:

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

input:

48 39
62.0000000000

output:

3
0.000000 0.000000
0.000000 0.413043
48.000000 39.000000

result:

ok correct

Test #28:

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

input:

98 94
135.9000000000

output:

3
0.000000 0.000000
0.000000 0.343795
98.000000 94.000000

result:

ok correct

Test #29:

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

input:

90 81
7290.0000000000

output:

177
0.000000 0.000000
0.000000 81.000000
1.000000 81.000000
1.000000 0.000000
2.000000 0.000000
2.000000 81.000000
3.000000 81.000000
3.000000 0.000000
4.000000 0.000000
4.000000 81.000000
5.000000 81.000000
5.000000 0.000000
6.000000 0.000000
6.000000 81.000000
7.000000 81.000000
7.000000 0.000000
...

result:

ok correct

Test #30:

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

input:

90 81
121.0826164250

output:

3
0.000000 0.000000
0.000000 0.000000
90.000000 81.000000

result:

ok correct

Test #31:

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

input:

34 99
3366.0000000000

output:

69
0.000000 0.000000
0.000000 99.000000
1.000000 99.000000
1.000000 0.000000
2.000000 0.000000
2.000000 99.000000
3.000000 99.000000
3.000000 0.000000
4.000000 0.000000
4.000000 99.000000
5.000000 99.000000
5.000000 0.000000
6.000000 0.000000
6.000000 99.000000
7.000000 99.000000
7.000000 0.000000
8...

result:

ok correct

Test #32:

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

input:

34 99
104.6756896330

output:

3
0.000000 0.000000
0.000000 0.000000
34.000000 99.000000

result:

ok correct

Test #33:

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

input:

3 3
5.9999

output:

3
0.000000 0.000000
0.000000 2.999900
3.000000 3.000000

result:

ok correct

Test #34:

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

input:

3 3
6.0

output:

3
0.000000 0.000000
0.000000 3.000000
3.000000 3.000000

result:

ok correct

Test #35:

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

input:

3 3
6.0001

output:

5
0.000000 0.000000
0.000000 3.000000
1.000000 3.000000
1.000000 2.999900
3.000000 3.000000

result:

ok correct

Test #36:

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

input:

4 4
13.999998

output:

5
0.000000 0.000000
0.000000 4.000000
1.000000 4.000000
1.000000 0.000001
4.000000 4.000000

result:

ok correct

Test #37:

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

input:

4 4
14.0

output:

5
0.000000 0.000000
0.000000 4.000000
1.000000 4.000000
1.000000 0.000000
4.000000 4.000000

result:

ok correct

Test #38:

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

input:

4 4
14.000002

output:

6
0.000000 0.000000
0.000000 4.000000
1.000000 4.000000
1.000000 0.000000
1.000005 0.000000
4.000000 4.000000

result:

ok correct

Test #39:

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

input:

4 4
15.123104

output:

7
0.000000 0.000000
0.000000 4.000000
1.000000 4.000000
1.000000 0.000000
2.000000 0.000000
2.000000 2.780773
4.000000 4.000000

result:

ok correct

Test #40:

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

input:

4 4
15.123106

output:

7
0.000000 0.000000
0.000000 4.000000
1.000000 4.000000
1.000000 0.000000
2.000000 0.000000
2.000000 2.780777
4.000000 4.000000

result:

ok correct

Test #41:

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

input:

4 4
15.123108

output:

7
0.000000 0.000000
0.000000 4.000000
1.000000 4.000000
1.000000 0.000000
2.000000 0.000000
2.000000 2.780781
4.000000 4.000000

result:

ok correct

Test #42:

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

input:

4 4
14.593385

output:

7
0.000000 0.000000
0.000000 4.000000
1.000000 4.000000
1.000000 0.000000
2.000000 0.000000
2.000000 0.926199
4.000000 4.000000

result:

ok correct

Test #43:

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

input:

4 4
14.593387

output:

7
0.000000 0.000000
0.000000 4.000000
1.000000 4.000000
1.000000 0.000000
2.000000 0.000000
2.000000 0.926212
4.000000 4.000000

result:

ok correct

Test #44:

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

input:

4 4
14.593389

output:

7
0.000000 0.000000
0.000000 4.000000
1.000000 4.000000
1.000000 0.000000
2.000000 0.000000
2.000000 0.926224
4.000000 4.000000

result:

ok correct

Test #45:

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

input:

2 2
4.0

output:

3
0.000000 0.000000
0.000000 2.000000
2.000000 2.000000

result:

ok correct

Test #46:

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

input:

3 3
5.0

output:

3
0.000000 0.000000
0.000000 1.750000
3.000000 3.000000

result:

ok correct

Test #47:

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

input:

4 4
15.123

output:

7
0.000000 0.000000
0.000000 4.000000
1.000000 4.000000
1.000000 0.000000
2.000000 0.000000
2.000000 2.780556
4.000000 4.000000

result:

ok correct

Test #48:

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

input:

4 4
14.1

output:

6
0.000000 0.000000
0.000000 4.000000
1.000000 4.000000
1.000000 0.000000
1.240476 0.000000
4.000000 4.000000

result:

ok correct

Test #49:

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

input:

3 3
9.0

output:

5
0.000000 0.000000
0.000000 3.000000
1.000000 3.000000
1.000000 0.900000
3.000000 3.000000

result:

ok correct

Test #50:

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

input:

4 4
16.0

output:

7
0.000000 0.000000
0.000000 4.000000
1.000000 4.000000
1.000000 0.000000
2.000000 0.000000
2.000000 4.000000
4.000000 4.000000

result:

ok correct