QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#305886#2290. Kinking CablesckisekiAC ✓1ms4096kbC++202.7kb2024-01-16 05:47:112024-01-16 05:47:11

Judging History

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

  • [2024-01-16 05:47:11]
  • 评测
  • 测评结果:AC
  • 用时:1ms
  • 内存:4096kb
  • [2024-01-16 05:47:11]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;
const int inf = 1e9;
using ll = int64_t;
using llf = long double;
const llf eps = 1e-8;

int n, m;
llf len;

bool in(llf x, llf L, llf R) {
    if (L > R)
        swap(L, R);
    return L <= x && x <= R;
}
long double dc(const function<llf(llf)> &func,
        llf l, llf r, llf fl, llf fr) {
    llf m = (l + r) / 2;
    llf fm = func(m);
    if (abs(fm - len) < eps) {
        return m;
    }
    if (in(len, fm, fl))
        return dc(func, l, m, fl, fm);
    else
        return dc(func, m, r, fm, fr);
}

pair<long double, bool>
proc(const function<llf(llf)> &func, llf l, llf r) {
    llf fl = func(l), fr = func(r);
    if (in(len, fl, fr)) {
        return { dc(func, l, r, fl, fr), true };
    } else {
        return { -1, false };
    }
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m >> len;
    vector<pair<llf,llf>> seg;

    const auto Output = [&seg]() {
        seg.emplace_back(n, m);
        // llf tot = 0;
        // for (int i = 1; i < (int)seg.size(); i++) {
        //     auto [x1, y1] = seg[i-1];
        //     auto [x2, y2] = seg[i];
        //     tot += hypot(x1-x2, y1-y2);
        // }
        // cerr << tot << endl;
        cout << seg.size() << '\n';
        cout << fixed << setprecision(10);
        for (auto [x, y]: seg) {
            cout << x << ' ' << y << '\n';
        }
        exit(0);
    };
    int len = 0;

    llf res;
    bool succ;
    for (int i = 0; i < n; i++) {
        if (i % 2 == 0) {
            seg.emplace_back(i, 0);
            tie(res, succ) = proc([&](llf t) {
                return len + t + hypot(n - i, m - (0 + t));
            }, 0, m);
            if (succ) {
                seg.emplace_back(i, 0 + res);
                Output();
            }
            seg.emplace_back(i, m);
            tie(res, succ) = proc([&](llf t) {
                return len + m + t + hypot(n - (i + t), m - m);
            }, 0, 1);
            if (succ) {
                seg.emplace_back(i + res, m);
                Output();
            }
        } else {
            seg.emplace_back(i, m);
            tie(res, succ) = proc([&](llf t) {
                return len + t + hypot(n - i, m - (m - t));
            }, 0, m);
            if (succ) {
                seg.emplace_back(i, m - res);
                Output();
            }
            seg.emplace_back(i, 0);
            tie(res, succ) = proc([&](llf t) {
                return len + m + t + hypot(n - (i + t), m - 0);
            }, 0, 1);
            if (succ) {
                seg.emplace_back(i + res, 0);
                Output();
            }
        }
        len += 1 + m;
    }
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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

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: 0ms
memory: 4068kb

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

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: 0ms
memory: 4000kb

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: 0ms
memory: 3976kb

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: 0ms
memory: 3984kb

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.1602695435
6.0000000000 8.0000000000

result:

ok correct

Test #8:

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

input:

5 5
7.1908428511

output:

3
0.0000000000 0.0000000000
0.0000000000 0.3898547590
5.0000000000 5.0000000000

result:

ok correct

Test #9:

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

input:

5 4
8.3927665498

output:

3
0.0000000000 0.0000000000
0.0000000000 3.3507961333
5.0000000000 4.0000000000

result:

ok correct

Test #10:

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

input:

4 2
6.4617533647

output:

5
0.0000000000 0.0000000000
0.0000000000 2.0000000000
1.0000000000 2.0000000000
1.0000000000 1.5690426230
4.0000000000 2.0000000000

result:

ok correct

Test #11:

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

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

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

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

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

input:

3 81
199.2077743610

output:

5
0.0000000000 0.0000000000
0.0000000000 81.0000000000
1.0000000000 81.0000000000
1.0000000000 22.4131765306
3.0000000000 81.0000000000

result:

ok correct

Test #16:

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

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.7311374912
4.0000000000 89.0000000000

result:

ok correct

Test #17:

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

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

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

input:

2 2
2.8284271248

output:

3
0.0000000000 0.0000000000
0.0000000000 0.0000000298
2.0000000000 2.0000000000

result:

ok correct

Test #20:

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

input:

100 100
10000.0000000000

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 #21:

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

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

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

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: 0ms
memory: 3996kb

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

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

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

input:

48 39
62.0000000000

output:

3
0.0000000000 0.0000000000
0.0000000000 0.4130434915
48.0000000000 39.0000000000

result:

ok correct

Test #28:

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

input:

98 94
135.9000000000

output:

3
0.0000000000 0.0000000000
0.0000000000 0.3437947817
98.0000000000 94.0000000000

result:

ok correct

Test #29:

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

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

input:

90 81
121.0826164250

output:

3
0.0000000000 0.0000000000
0.0000000000 0.0000000189
90.0000000000 81.0000000000

result:

ok correct

Test #31:

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

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: 0ms
memory: 3924kb

input:

34 99
104.6756896330

output:

3
0.0000000000 0.0000000000
0.0000000000 0.0000001844
34.0000000000 99.0000000000

result:

ok correct

Test #33:

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

input:

3 3
5.9999

output:

3
0.0000000000 0.0000000000
0.0000000000 2.9998999983
3.0000000000 3.0000000000

result:

ok correct

Test #34:

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

input:

3 3
6.0

output:

3
0.0000000000 0.0000000000
0.0000000000 2.9999999944
3.0000000000 3.0000000000

result:

ok correct

Test #35:

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

input:

3 3
6.0001

output:

5
0.0000000000 0.0000000000
0.0000000000 3.0000000000
1.0000000000 3.0000000000
1.0000000000 2.9998999983
3.0000000000 3.0000000000

result:

ok correct

Test #36:

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

input:

4 4
13.999998

output:

5
0.0000000000 0.0000000000
0.0000000000 4.0000000000
1.0000000000 4.0000000000
1.0000000000 0.0000011101
4.0000000000 4.0000000000

result:

ok correct

Test #37:

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

input:

4 4
14.0

output:

5
0.0000000000 0.0000000000
0.0000000000 4.0000000000
1.0000000000 4.0000000000
1.0000000000 0.0000000037
4.0000000000 4.0000000000

result:

ok correct

Test #38:

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

input:

4 4
14.000002

output:

6
0.0000000000 0.0000000000
0.0000000000 4.0000000000
1.0000000000 4.0000000000
1.0000000000 0.0000000000
1.0000050068 0.0000000000
4.0000000000 4.0000000000

result:

ok correct

Test #39:

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

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.7807730138
4.0000000000 4.0000000000

result:

ok correct

Test #40:

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

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.7807771862
4.0000000000 4.0000000000

result:

ok correct

Test #41:

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

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.7807813585
4.0000000000 4.0000000000

result:

ok correct

Test #42:

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

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.9261994362
4.0000000000 4.0000000000

result:

ok correct

Test #43:

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

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.9262118340
4.0000000000 4.0000000000

result:

ok correct

Test #44:

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

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.9262242317
4.0000000000 4.0000000000

result:

ok correct

Test #45:

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

input:

2 2
4.0

output:

3
0.0000000000 0.0000000000
0.0000000000 1.9999999925
2.0000000000 2.0000000000

result:

ok correct

Test #46:

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

input:

3 3
5.0

output:

3
0.0000000000 0.0000000000
0.0000000000 1.7499999851
3.0000000000 3.0000000000

result:

ok correct

Test #47:

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

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.7805560827
4.0000000000 4.0000000000

result:

ok correct

Test #48:

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

input:

4 4
14.1

output:

6
0.0000000000 0.0000000000
0.0000000000 4.0000000000
1.0000000000 4.0000000000
1.0000000000 0.0000000000
1.2404761910 0.0000000000
4.0000000000 4.0000000000

result:

ok correct

Test #49:

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

input:

3 3
9.0

output:

5
0.0000000000 0.0000000000
0.0000000000 3.0000000000
1.0000000000 3.0000000000
1.0000000000 0.9000000022
3.0000000000 3.0000000000

result:

ok correct

Test #50:

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

input:

4 4
16.0

output:

7
0.0000000000 0.0000000000
0.0000000000 4.0000000000
1.0000000000 4.0000000000
1.0000000000 0.0000000000
2.0000000000 0.0000000000
2.0000000000 3.9999999925
4.0000000000 4.0000000000

result:

ok correct