QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#636347#2290. Kinking Cablesoxford01#AC ✓7ms4080kbC++203.1kb2024-10-12 23:29:372024-10-12 23:29:41

Judging History

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

  • [2024-10-12 23:29:41]
  • 评测
  • 测评结果:AC
  • 用时:7ms
  • 内存:4080kb
  • [2024-10-12 23:29:37]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

#define rep(i, a, b) for (auto i = a; i < (b); ++i)
#define repr(i, a, b) for (auto i = (a) - 1; i >= (b); --i)
#define pb push_back
#define eb emplace_back
#define all(x) begin(x), end(x)
#define sz(x) int((x).size())

using ll = long long;
using pii = pair<int, int>;
using vi = vector<int>;
using vll = vector<ll>;
using vii = vector<pii>;

template<class T>
inline bool cmax(T &a, const T &b) {
    return a < b ? a = b, 1 : 0;
}

template<class T>
inline bool cmin(T &a, const T &b) {
    return b < a ? a = b, 1 : 0;
}

const int inf = 0x3f3f3f3f;
const ll linf = 1e18;
const double dinf = numeric_limits<double>::infinity();

using ld = long double;

int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin.exceptions(cin.failbit);
    
    int n, m;
    cin >> n >> m;
    ld l;
    cin >> l;

    auto len = [&](vector< pair<ld, ld> > p) {
        sort(all(p), [&](const auto &a, const auto &b) {
            return a.second < b.second;
        });
        ld ans = 0;
        rep(i, 1, sz(p)) {
            ans += hypotl(p[i].first - p[i - 1].first, p[i].second - p[i - 1].second);
        }
        return ans;
    };

    vector< pair<ld, ld> > p = {{0, 0}, {n, m}};
    ld L = hypotl(n, m);
    vector< pair<ld, ld> > q;
    if (m % 2 == 1) {
        rep(i, 1, m) {
            if (i % 2 == 1) {
                q.eb(n, i);
            } else {
                q.eb(0, i);
            }
        }
    } else {
        rep(i, 1, m - 1) {
            if (i % 2 == 1) {
                q.eb(n, i);
            } else {
                q.eb(0, i);
            }
        }
        q.eb(n, m - 2 + 2.l / 3);
        q.eb(0, m - 2 + 4.l / 3);
    }

    ld lx = 0, ly = 0;
    for (auto &[y, x] : q) {
        auto tmp = p;
        tmp.eb(y, x);
        // cerr << len(tmp) << endl;
        if (len(tmp) < l - 1e-9) {
            p.eb(y, x);
            lx = x;
            ly = y;
            continue;
        }

        ld ty = ly + (x - lx) / (m - lx) * (n - ly);
        ld lo = y, hi = ty;
        int invert = 0;
        if (lo > hi) {
            invert = 1;
            swap(lo, hi);
        }

        while (hi - lo > 1e-9) {
            ld mid = (lo + hi) / 2;
            tmp = p;
            tmp.eb(mid, x);
            // cerr << mid << ' ' << len(tmp) << endl;
            if (len(tmp) > l) {
                if (invert) {
                    hi = mid;
                } else {
                    lo = mid;
                }
            } else {
                if (invert) {
                    lo = mid;
                } else {
                    hi = mid;
                }
            }
        }
        p.eb(lo, x);
        break;
        // ld ty = ly + (m - lx) * (m - ly);
    }

    sort(all(p), [&](const auto &a, const auto &b) {
        return a.second < b.second;
    });

    cout << sz(p) << '\n';
    cout << fixed << setprecision(15);
    for (auto &[x, y] : p) {
        cout << x << ' ' << y << '\n';
    }

    // cerr << len(p) << endl;

    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 4000kb

input:

79 78
1980.7712136406

output:

26
0.000000000000000 0.000000000000000
79.000000000000000 1.000000000000000
0.000000000000000 2.000000000000000
79.000000000000000 3.000000000000000
0.000000000000000 4.000000000000000
79.000000000000000 5.000000000000000
0.000000000000000 6.000000000000000
79.000000000000000 7.000000000000000
0.000...

result:

ok correct

Test #2:

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

input:

33 65
1947.7601065763

output:

60
0.000000000000000 0.000000000000000
33.000000000000000 1.000000000000000
0.000000000000000 2.000000000000000
33.000000000000000 3.000000000000000
0.000000000000000 4.000000000000000
33.000000000000000 5.000000000000000
0.000000000000000 6.000000000000000
33.000000000000000 7.000000000000000
0.000...

result:

ok correct

Test #3:

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

input:

51 51
555.0803652025

output:

12
0.000000000000000 0.000000000000000
51.000000000000000 1.000000000000000
0.000000000000000 2.000000000000000
51.000000000000000 3.000000000000000
0.000000000000000 4.000000000000000
51.000000000000000 5.000000000000000
0.000000000000000 6.000000000000000
51.000000000000000 7.000000000000000
0.000...

result:

ok correct

Test #4:

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

input:

49 2
67.3588717350

output:

4
0.000000000000000 0.000000000000000
49.000000000000000 0.666666666666667
39.847078314764076 1.333333333333333
49.000000000000000 2.000000000000000

result:

ok correct

Test #5:

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

input:

37 48
1713.3643608504

output:

48
0.000000000000000 0.000000000000000
37.000000000000000 1.000000000000000
0.000000000000000 2.000000000000000
37.000000000000000 3.000000000000000
0.000000000000000 4.000000000000000
37.000000000000000 5.000000000000000
0.000000000000000 6.000000000000000
37.000000000000000 7.000000000000000
0.000...

result:

ok correct

Test #6:

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

input:

51 79
820.1218304546

output:

17
0.000000000000000 0.000000000000000
51.000000000000000 1.000000000000000
0.000000000000000 2.000000000000000
51.000000000000000 3.000000000000000
0.000000000000000 4.000000000000000
51.000000000000000 5.000000000000000
0.000000000000000 6.000000000000000
51.000000000000000 7.000000000000000
0.000...

result:

ok correct

Test #7:

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

input:

6 8
37.5338494218

output:

8
0.000000000000000 0.000000000000000
6.000000000000000 1.000000000000000
0.000000000000000 2.000000000000000
6.000000000000000 3.000000000000000
0.000000000000000 4.000000000000000
6.000000000000000 5.000000000000000
2.803421508986503 6.000000000000000
6.000000000000000 8.000000000000000

result:

ok correct

Test #8:

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

input:

5 5
7.1908428511

output:

3
0.000000000000000 0.000000000000000
1.836334371939301 1.000000000000000
5.000000000000000 5.000000000000000

result:

ok correct

Test #9:

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

input:

5 4
8.3927665498

output:

4
0.000000000000000 0.000000000000000
5.000000000000000 1.000000000000000
4.352242964669131 2.000000000000000
5.000000000000000 4.000000000000000

result:

ok correct

Test #10:

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

input:

4 2
6.4617533647

output:

4
0.000000000000000 0.000000000000000
4.000000000000000 0.666666666666667
2.998271299526095 1.333333333333333
4.000000000000000 2.000000000000000

result:

ok correct

Test #11:

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

input:

91 87
4830.8473359767

output:

55
0.000000000000000 0.000000000000000
91.000000000000000 1.000000000000000
0.000000000000000 2.000000000000000
91.000000000000000 3.000000000000000
0.000000000000000 4.000000000000000
91.000000000000000 5.000000000000000
0.000000000000000 6.000000000000000
91.000000000000000 7.000000000000000
0.000...

result:

ok correct

Test #12:

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

input:

90 90
5088.9280941138

output:

58
0.000000000000000 0.000000000000000
90.000000000000000 1.000000000000000
0.000000000000000 2.000000000000000
90.000000000000000 3.000000000000000
0.000000000000000 4.000000000000000
90.000000000000000 5.000000000000000
0.000000000000000 6.000000000000000
90.000000000000000 7.000000000000000
0.000...

result:

ok correct

Test #13:

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

input:

90 92
7004.0153432299

output:

80
0.000000000000000 0.000000000000000
90.000000000000000 1.000000000000000
0.000000000000000 2.000000000000000
90.000000000000000 3.000000000000000
0.000000000000000 4.000000000000000
90.000000000000000 5.000000000000000
0.000000000000000 6.000000000000000
90.000000000000000 7.000000000000000
0.000...

result:

ok correct

Test #14:

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

input:

91 83
1879.3819547895

output:

22
0.000000000000000 0.000000000000000
91.000000000000000 1.000000000000000
0.000000000000000 2.000000000000000
91.000000000000000 3.000000000000000
0.000000000000000 4.000000000000000
91.000000000000000 5.000000000000000
0.000000000000000 6.000000000000000
91.000000000000000 7.000000000000000
0.000...

result:

ok correct

Test #15:

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

input:

3 81
199.2077743610

output:

57
0.000000000000000 0.000000000000000
3.000000000000000 1.000000000000000
0.000000000000000 2.000000000000000
3.000000000000000 3.000000000000000
0.000000000000000 4.000000000000000
3.000000000000000 5.000000000000000
0.000000000000000 6.000000000000000
3.000000000000000 7.000000000000000
0.0000000...

result:

ok correct

Test #16:

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

input:

4 89
288.5915130114

output:

66
0.000000000000000 0.000000000000000
4.000000000000000 1.000000000000000
0.000000000000000 2.000000000000000
4.000000000000000 3.000000000000000
0.000000000000000 4.000000000000000
4.000000000000000 5.000000000000000
0.000000000000000 6.000000000000000
4.000000000000000 7.000000000000000
0.0000000...

result:

ok correct

Test #17:

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

input:

95 3
175.9210001082

output:

4
0.000000000000000 0.000000000000000
95.000000000000000 1.000000000000000
54.554491874987434 2.000000000000000
95.000000000000000 3.000000000000000

result:

ok correct

Test #18:

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

input:

84 4
310.3037172015

output:

6
0.000000000000000 0.000000000000000
84.000000000000000 1.000000000000000
0.000000000000000 2.000000000000000
84.000000000000000 2.666666666666667
54.863042118027806 3.333333333333333
84.000000000000000 4.000000000000000

result:

ok correct

Test #19:

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

input:

2 2
2.8284271248

output:

3
0.000000000000000 0.000000000000000
0.666678297643860 0.666666666666667
2.000000000000000 2.000000000000000

result:

ok correct

Test #20:

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

input:

100 100
10000.0000000000

output:

102
0.000000000000000 0.000000000000000
100.000000000000000 1.000000000000000
0.000000000000000 2.000000000000000
100.000000000000000 3.000000000000000
0.000000000000000 4.000000000000000
100.000000000000000 5.000000000000000
0.000000000000000 6.000000000000000
100.000000000000000 7.000000000000000
...

result:

ok correct

Test #21:

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

input:

100 100
9999.2500000000

output:

102
0.000000000000000 0.000000000000000
100.000000000000000 1.000000000000000
0.000000000000000 2.000000000000000
100.000000000000000 3.000000000000000
0.000000000000000 4.000000000000000
100.000000000000000 5.000000000000000
0.000000000000000 6.000000000000000
100.000000000000000 7.000000000000000
...

result:

ok correct

Test #22:

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

input:

100 100
2723.8981892905

output:

28
0.000000000000000 0.000000000000000
100.000000000000000 1.000000000000000
0.000000000000000 2.000000000000000
100.000000000000000 3.000000000000000
0.000000000000000 4.000000000000000
100.000000000000000 5.000000000000000
0.000000000000000 6.000000000000000
100.000000000000000 7.000000000000000
0...

result:

ok correct

Test #23:

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

input:

100 100
8994.4904261819

output:

92
0.000000000000000 0.000000000000000
100.000000000000000 1.000000000000000
0.000000000000000 2.000000000000000
100.000000000000000 3.000000000000000
0.000000000000000 4.000000000000000
100.000000000000000 5.000000000000000
0.000000000000000 6.000000000000000
100.000000000000000 7.000000000000000
0...

result:

ok correct

Test #24:

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

input:

100 100
881.4998747190

output:

10
0.000000000000000 0.000000000000000
100.000000000000000 1.000000000000000
0.000000000000000 2.000000000000000
100.000000000000000 3.000000000000000
0.000000000000000 4.000000000000000
100.000000000000000 5.000000000000000
0.000000000000000 6.000000000000000
100.000000000000000 7.000000000000000
3...

result:

ok correct

Test #25:

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

input:

88 94
8266.2500000000

output:

96
0.000000000000000 0.000000000000000
88.000000000000000 1.000000000000000
0.000000000000000 2.000000000000000
88.000000000000000 3.000000000000000
0.000000000000000 4.000000000000000
88.000000000000000 5.000000000000000
0.000000000000000 6.000000000000000
88.000000000000000 7.000000000000000
0.000...

result:

ok correct

Test #26:

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

input:

75 37
2772.0000000000

output:

38
0.000000000000000 0.000000000000000
75.000000000000000 1.000000000000000
0.000000000000000 2.000000000000000
75.000000000000000 3.000000000000000
0.000000000000000 4.000000000000000
75.000000000000000 5.000000000000000
0.000000000000000 6.000000000000000
75.000000000000000 7.000000000000000
0.000...

result:

ok correct

Test #27:

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

input:

48 39
62.0000000000

output:

3
0.000000000000000 0.000000000000000
2.659090908781554 1.000000000000000
48.000000000000000 39.000000000000000

result:

ok correct

Test #28:

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

input:

98 94
135.9000000000

output:

3
0.000000000000000 0.000000000000000
2.022096045488650 1.000000000000000
98.000000000000000 94.000000000000000

result:

ok correct

Test #29:

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

input:

90 81
7290.0000000000

output:

82
0.000000000000000 0.000000000000000
90.000000000000000 1.000000000000000
0.000000000000000 2.000000000000000
90.000000000000000 3.000000000000000
0.000000000000000 4.000000000000000
90.000000000000000 5.000000000000000
0.000000000000000 6.000000000000000
90.000000000000000 7.000000000000000
0.000...

result:

ok correct

Test #30:

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

input:

90 81
121.0826164250

output:

3
0.000000000000000 0.000000000000000
1.111205023351229 1.000000000000000
90.000000000000000 81.000000000000000

result:

ok correct

Test #31:

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

input:

34 99
3366.0000000000

output:

100
0.000000000000000 0.000000000000000
34.000000000000000 1.000000000000000
0.000000000000000 2.000000000000000
34.000000000000000 3.000000000000000
0.000000000000000 4.000000000000000
34.000000000000000 5.000000000000000
0.000000000000000 6.000000000000000
34.000000000000000 7.000000000000000
0.00...

result:

ok correct

Test #32:

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

input:

34 99
104.6756896330

output:

3
0.000000000000000 0.000000000000000
0.343474483798314 1.000000000000000
34.000000000000000 99.000000000000000

result:

ok correct

Test #33:

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

input:

3 3
5.9999

output:

4
0.000000000000000 0.000000000000000
3.000000000000000 1.000000000000000
1.993508501211181 2.000000000000000
3.000000000000000 3.000000000000000

result:

ok correct

Test #34:

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

input:

3 3
6.0

output:

4
0.000000000000000 0.000000000000000
3.000000000000000 1.000000000000000
1.993438019882888 2.000000000000000
3.000000000000000 3.000000000000000

result:

ok correct

Test #35:

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

input:

3 3
6.0001

output:

4
0.000000000000000 0.000000000000000
3.000000000000000 1.000000000000000
1.993367540650070 2.000000000000000
3.000000000000000 3.000000000000000

result:

ok correct

Test #36:

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

input:

4 4
13.999998

output:

6
0.000000000000000 0.000000000000000
4.000000000000000 1.000000000000000
0.000000000000000 2.000000000000000
4.000000000000000 2.666666666666667
3.473809913732111 3.333333333333333
4.000000000000000 4.000000000000000

result:

ok correct

Test #37:

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

input:

4 4
14.0

output:

6
0.000000000000000 0.000000000000000
4.000000000000000 1.000000000000000
0.000000000000000 2.000000000000000
4.000000000000000 2.666666666666667
3.473808299750090 3.333333333333333
4.000000000000000 4.000000000000000

result:

ok correct

Test #38:

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

input:

4 4
14.000002

output:

6
0.000000000000000 0.000000000000000
4.000000000000000 1.000000000000000
0.000000000000000 2.000000000000000
4.000000000000000 2.666666666666667
3.473806685768068 3.333333333333333
4.000000000000000 4.000000000000000

result:

ok correct

Test #39:

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

input:

4 4
15.123104

output:

6
0.000000000000000 0.000000000000000
4.000000000000000 1.000000000000000
0.000000000000000 2.000000000000000
4.000000000000000 2.666666666666667
2.756586033850908 3.333333333333333
4.000000000000000 4.000000000000000

result:

ok correct

Test #40:

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

input:

4 4
15.123106

output:

6
0.000000000000000 0.000000000000000
4.000000000000000 1.000000000000000
0.000000000000000 2.000000000000000
4.000000000000000 2.666666666666667
2.756584898568690 3.333333333333333
4.000000000000000 4.000000000000000

result:

ok correct

Test #41:

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

input:

4 4
15.123108

output:

6
0.000000000000000 0.000000000000000
4.000000000000000 1.000000000000000
0.000000000000000 2.000000000000000
4.000000000000000 2.666666666666667
2.756583764217794 3.333333333333333
4.000000000000000 4.000000000000000

result:

ok correct

Test #42:

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

input:

4 4
14.593385

output:

6
0.000000000000000 0.000000000000000
4.000000000000000 1.000000000000000
0.000000000000000 2.000000000000000
4.000000000000000 2.666666666666667
3.067867982201278 3.333333333333333
4.000000000000000 4.000000000000000

result:

ok correct

Test #43:

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

input:

4 4
14.593387

output:

6
0.000000000000000 0.000000000000000
4.000000000000000 1.000000000000000
0.000000000000000 2.000000000000000
4.000000000000000 2.666666666666667
3.067866751924157 3.333333333333333
4.000000000000000 4.000000000000000

result:

ok correct

Test #44:

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

input:

4 4
14.593389

output:

6
0.000000000000000 0.000000000000000
4.000000000000000 1.000000000000000
0.000000000000000 2.000000000000000
4.000000000000000 2.666666666666667
3.067865522578359 3.333333333333333
4.000000000000000 4.000000000000000

result:

ok correct

Test #45:

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

input:

2 2
4.0

output:

4
0.000000000000000 0.000000000000000
2.000000000000000 0.666666666666667
1.328958679921925 1.333333333333333
2.000000000000000 2.000000000000000

result:

ok correct

Test #46:

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

input:

3 3
5.0

output:

3
0.000000000000000 0.000000000000000
2.819836056791246 1.000000000000000
3.000000000000000 3.000000000000000

result:

ok correct

Test #47:

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

input:

4 4
15.123

output:

6
0.000000000000000 0.000000000000000
4.000000000000000 1.000000000000000
0.000000000000000 2.000000000000000
4.000000000000000 2.666666666666667
2.756645036861300 3.333333333333333
4.000000000000000 4.000000000000000

result:

ok correct

Test #48:

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

input:

4 4
14.1

output:

6
0.000000000000000 0.000000000000000
4.000000000000000 1.000000000000000
0.000000000000000 2.000000000000000
4.000000000000000 2.666666666666667
3.396420351229608 3.333333333333333
4.000000000000000 4.000000000000000

result:

ok correct

Test #49:

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

input:

3 3
9.0

output:

4
0.000000000000000 0.000000000000000
3.000000000000000 1.000000000000000
0.257783645996824 2.000000000000000
3.000000000000000 3.000000000000000

result:

ok correct

Test #50:

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

input:

4 4
16.0

output:

6
0.000000000000000 0.000000000000000
4.000000000000000 1.000000000000000
0.000000000000000 2.000000000000000
4.000000000000000 2.666666666666667
2.275038714520633 3.333333333333333
4.000000000000000 4.000000000000000

result:

ok correct