QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#31494#2290. Kinking CablesVingying0#AC ✓6ms3916kbC++172.4kb2022-05-08 14:44:232022-05-08 14:44:24

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-05-08 14:44:24]
  • 评测
  • 测评结果:AC
  • 用时:6ms
  • 内存:3916kb
  • [2022-05-08 14:44:23]
  • 提交

answer

#include "bits/stdc++.h"
using namespace std;
const int N = 105;
using db = long double;

int n, m;
db len;
using pdb = pair<db, db>;
vector<pdb> ans;
const db eps = 1e-9;
int dcmp(const db &x) {
    return abs(x) < 1e-5?0:(x < 0?-1:1);
}
db x = 0, y = 0, lx = 0, ly = 0;
db dist(db x,db y, db _x,db _y) {
    return sqrtl((x-_x)*(x-_x)+(y-_y)*(y-_y));
}
void add(db x, db y) {
    ::x = x, ::y = y;
    ans.push_back({x, y});
    len -= dist(::x, ::y, lx, ly);
    lx = x, ly = y;
}


void solve()
{
    add(x, y);
    int f = 0;
    while (len > 1e-9)
    {
        if (f == 0) {
            if (dcmp(n + m - x - len) != -1) {
                db mx = (x + m) / 2, my = (y + n) / 2;
                db d = dist(mx, my, m, 0);
                db vx = -(m - mx) / d, vy = my / d;
                db l = 0, r = d;
                db nx, ny;
                while((r - l)>eps) {
                    db mid = (l + r) / 2;
                    nx = m + vx * mid, ny = vy * mid;
                    if (dist(nx, ny, x, y) + dist(nx, ny, m, n) > len) {
                        l = mid;
                    }
                    else r = mid;
                }
                add(nx, ny);
                break;
            }
            else {
                y = n;
                add(x, y);
            }
        } else {
            if (dcmp(sqrt(1+n*n)+dist(x+1,0,m,n) - len) != -1) {
                db mx = x + 1, my = y;
                db vx = 0, vy = -1;
                db l = 0, r = n;
                db nx, ny;
                while((r - l)>eps) {
                    db mid = (l + r) / 2;
                    nx = mx + vx * mid, ny = my + vy * mid;
                    if (dist(nx, ny, x, y) + dist(nx, ny, m, n) < len) {
                        l = mid;
                    }
                    else r = mid;
                }
                add(nx, ny);
                break;
            }
            else {
                x++, y=0;
                add(x, y);
            }
        }
        f ^= 1;
    }
    add(m, n);

}

int main()
{
    cout << fixed << setprecision(10);
    cin >> n >> m >> len;
    solve();
    cout << ans.size() << "\n";
    for (auto [px, py] : ans)
    {
        cout << py << " " << px << "\n";
    }
    cout.flush();
    assert(dcmp(len) == 0);
//    cerr << len << endl;
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

79 78
1980.7712136406

output:

26
0.0000000000 0.0000000000
79.0000000000 0.0000000000
0.0000000000 1.0000000000
79.0000000000 1.0000000000
0.0000000000 2.0000000000
79.0000000000 2.0000000000
0.0000000000 3.0000000000
79.0000000000 3.0000000000
0.0000000000 4.0000000000
79.0000000000 4.0000000000
0.0000000000 5.0000000000
79.000...

result:

ok correct

Test #2:

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

input:

33 65
1947.7601065763

output:

60
0.0000000000 0.0000000000
33.0000000000 0.0000000000
0.0000000000 1.0000000000
33.0000000000 1.0000000000
0.0000000000 2.0000000000
33.0000000000 2.0000000000
0.0000000000 3.0000000000
33.0000000000 3.0000000000
0.0000000000 4.0000000000
33.0000000000 4.0000000000
0.0000000000 5.0000000000
33.000...

result:

ok correct

Test #3:

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

input:

51 51
555.0803652025

output:

12
0.0000000000 0.0000000000
51.0000000000 0.0000000000
0.0000000000 1.0000000000
51.0000000000 1.0000000000
0.0000000000 2.0000000000
51.0000000000 2.0000000000
0.0000000000 3.0000000000
51.0000000000 3.0000000000
0.0000000000 4.0000000000
51.0000000000 4.0000000000
14.0038406518 5.0000000000
51.00...

result:

ok correct

Test #4:

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

input:

49 2
67.3588717350

output:

4
0.0000000000 0.0000000000
49.0000000000 0.0000000000
39.8751962847 1.0000000000
49.0000000000 2.0000000000

result:

ok correct

Test #5:

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

input:

37 48
1713.3643608504

output:

48
0.0000000000 0.0000000000
37.0000000000 0.0000000000
0.0000000000 1.0000000000
37.0000000000 1.0000000000
0.0000000000 2.0000000000
37.0000000000 2.0000000000
0.0000000000 3.0000000000
37.0000000000 3.0000000000
0.0000000000 4.0000000000
37.0000000000 4.0000000000
0.0000000000 5.0000000000
37.000...

result:

ok correct

Test #6:

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

input:

51 79
820.1218304546

output:

17
0.0000000000 0.0000000000
51.0000000000 0.0000000000
0.0000000000 1.0000000000
51.0000000000 1.0000000000
0.0000000000 2.0000000000
51.0000000000 2.0000000000
0.0000000000 3.0000000000
51.0000000000 3.0000000000
0.0000000000 4.0000000000
51.0000000000 4.0000000000
0.0000000000 5.0000000000
51.000...

result:

ok correct

Test #7:

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

input:

6 8
37.5338494218

output:

8
0.0000000000 0.0000000000
6.0000000000 0.0000000000
0.0000000000 1.0000000000
6.0000000000 1.0000000000
0.0000000000 2.0000000000
6.0000000000 2.0000000000
4.2040697455 3.0000000000
6.0000000000 8.0000000000

result:

ok correct

Test #8:

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

input:

5 5
7.1908428511

output:

3
0.0000000000 0.0000000000
2.0379095181 2.9620904819
5.0000000000 5.0000000000

result:

ok correct

Test #9:

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

input:

5 4
8.3927665498

output:

3
0.0000000000 0.0000000000
0.3512614529 3.7189908377
5.0000000000 4.0000000000

result:

ok correct

Test #10:

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

input:

4 2
6.4617533647

output:

4
0.0000000000 0.0000000000
4.0000000000 0.0000000000
3.2823249986 1.0000000000
4.0000000000 2.0000000000

result:

ok correct

Test #11:

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

input:

91 87
4830.8473359767

output:

54
0.0000000000 0.0000000000
91.0000000000 0.0000000000
0.0000000000 1.0000000000
91.0000000000 1.0000000000
0.0000000000 2.0000000000
91.0000000000 2.0000000000
0.0000000000 3.0000000000
91.0000000000 3.0000000000
0.0000000000 4.0000000000
91.0000000000 4.0000000000
0.0000000000 5.0000000000
91.000...

result:

ok correct

Test #12:

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

input:

90 90
5088.9280941138

output:

58
0.0000000000 0.0000000000
90.0000000000 0.0000000000
0.0000000000 1.0000000000
90.0000000000 1.0000000000
0.0000000000 2.0000000000
90.0000000000 2.0000000000
0.0000000000 3.0000000000
90.0000000000 3.0000000000
0.0000000000 4.0000000000
90.0000000000 4.0000000000
0.0000000000 5.0000000000
90.000...

result:

ok correct

Test #13:

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

input:

90 92
7004.0153432299

output:

80
0.0000000000 0.0000000000
90.0000000000 0.0000000000
0.0000000000 1.0000000000
90.0000000000 1.0000000000
0.0000000000 2.0000000000
90.0000000000 2.0000000000
0.0000000000 3.0000000000
90.0000000000 3.0000000000
0.0000000000 4.0000000000
90.0000000000 4.0000000000
0.0000000000 5.0000000000
90.000...

result:

ok correct

Test #14:

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

input:

91 83
1879.3819547895

output:

22
0.0000000000 0.0000000000
91.0000000000 0.0000000000
0.0000000000 1.0000000000
91.0000000000 1.0000000000
0.0000000000 2.0000000000
91.0000000000 2.0000000000
0.0000000000 3.0000000000
91.0000000000 3.0000000000
0.0000000000 4.0000000000
91.0000000000 4.0000000000
0.0000000000 5.0000000000
91.000...

result:

ok correct

Test #15:

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

input:

3 81
199.2077743610

output:

48
0.0000000000 0.0000000000
3.0000000000 0.0000000000
0.0000000000 1.0000000000
3.0000000000 1.0000000000
0.0000000000 2.0000000000
3.0000000000 2.0000000000
0.0000000000 3.0000000000
3.0000000000 3.0000000000
0.0000000000 4.0000000000
3.0000000000 4.0000000000
0.0000000000 5.0000000000
3.000000000...

result:

ok correct

Test #16:

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

input:

4 89
288.5915130114

output:

59
0.0000000000 0.0000000000
4.0000000000 0.0000000000
0.0000000000 1.0000000000
4.0000000000 1.0000000000
0.0000000000 2.0000000000
4.0000000000 2.0000000000
0.0000000000 3.0000000000
4.0000000000 3.0000000000
0.0000000000 4.0000000000
4.0000000000 4.0000000000
0.0000000000 5.0000000000
4.000000000...

result:

ok correct

Test #17:

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

input:

95 3
175.9210001082

output:

4
0.0000000000 0.0000000000
95.0000000000 0.0000000000
54.5704018294 1.0000000000
95.0000000000 3.0000000000

result:

ok correct

Test #18:

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

input:

84 4
310.3037172015

output:

6
0.0000000000 0.0000000000
84.0000000000 0.0000000000
0.0000000000 1.0000000000
84.0000000000 1.0000000000
54.8940209935 2.0000000000
84.0000000000 4.0000000000

result:

ok correct

Test #19:

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

input:

2 2
2.8284271248

output:

3
0.0000000000 0.0000000000
0.9999938314 1.0000061686
2.0000000000 2.0000000000

result:

ok correct

Test #20:

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

input:

100 100
10000.0000000000

output:

102
0.0000000000 0.0000000000
100.0000000000 0.0000000000
0.0000000000 1.0000000000
100.0000000000 1.0000000000
0.0000000000 2.0000000000
100.0000000000 2.0000000000
0.0000000000 3.0000000000
100.0000000000 3.0000000000
0.0000000000 4.0000000000
100.0000000000 4.0000000000
0.0000000000 5.0000000000
...

result:

ok correct

Test #21:

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

input:

100 100
9999.2500000000

output:

102
0.0000000000 0.0000000000
100.0000000000 0.0000000000
0.0000000000 1.0000000000
100.0000000000 1.0000000000
0.0000000000 2.0000000000
100.0000000000 2.0000000000
0.0000000000 3.0000000000
100.0000000000 3.0000000000
0.0000000000 4.0000000000
100.0000000000 4.0000000000
0.0000000000 5.0000000000
...

result:

ok correct

Test #22:

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

input:

100 100
2723.8981892905

output:

28
0.0000000000 0.0000000000
100.0000000000 0.0000000000
0.0000000000 1.0000000000
100.0000000000 1.0000000000
0.0000000000 2.0000000000
100.0000000000 2.0000000000
0.0000000000 3.0000000000
100.0000000000 3.0000000000
0.0000000000 4.0000000000
100.0000000000 4.0000000000
0.0000000000 5.0000000000
1...

result:

ok correct

Test #23:

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

input:

100 100
8994.4904261819

output:

92
0.0000000000 0.0000000000
100.0000000000 0.0000000000
0.0000000000 1.0000000000
100.0000000000 1.0000000000
0.0000000000 2.0000000000
100.0000000000 2.0000000000
0.0000000000 3.0000000000
100.0000000000 3.0000000000
0.0000000000 4.0000000000
100.0000000000 4.0000000000
0.0000000000 5.0000000000
1...

result:

ok correct

Test #24:

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

input:

100 100
881.4998747190

output:

10
0.0000000000 0.0000000000
100.0000000000 0.0000000000
0.0000000000 1.0000000000
100.0000000000 1.0000000000
0.0000000000 2.0000000000
100.0000000000 2.0000000000
0.0000000000 3.0000000000
100.0000000000 3.0000000000
34.6530040340 4.0000000000
100.0000000000 100.0000000000

result:

ok correct

Test #25:

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

input:

88 94
8266.2500000000

output:

96
0.0000000000 0.0000000000
88.0000000000 0.0000000000
0.0000000000 1.0000000000
88.0000000000 1.0000000000
0.0000000000 2.0000000000
88.0000000000 2.0000000000
0.0000000000 3.0000000000
88.0000000000 3.0000000000
0.0000000000 4.0000000000
88.0000000000 4.0000000000
0.0000000000 5.0000000000
88.000...

result:

ok correct

Test #26:

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

input:

75 37
2772.0000000000

output:

38
0.0000000000 0.0000000000
75.0000000000 0.0000000000
0.0000000000 1.0000000000
75.0000000000 1.0000000000
0.0000000000 2.0000000000
75.0000000000 2.0000000000
0.0000000000 3.0000000000
75.0000000000 3.0000000000
0.0000000000 4.0000000000
75.0000000000 4.0000000000
0.0000000000 5.0000000000
75.000...

result:

ok correct

Test #27:

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

input:

48 39
62.0000000000

output:

3
0.0000000000 0.0000000000
22.2720905354 20.9039264400
48.0000000000 39.0000000000

result:

ok correct

Test #28:

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

input:

98 94
135.9000000000

output:

3
0.0000000000 0.0000000000
47.0615096025 48.8593683404
98.0000000000 94.0000000000

result:

ok correct

Test #29:

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

input:

90 81
7290.0000000000

output:

82
0.0000000000 0.0000000000
90.0000000000 0.0000000000
0.0000000000 1.0000000000
90.0000000000 1.0000000000
0.0000000000 2.0000000000
90.0000000000 2.0000000000
0.0000000000 3.0000000000
90.0000000000 3.0000000000
0.0000000000 4.0000000000
90.0000000000 4.0000000000
0.0000000000 5.0000000000
90.000...

result:

ok correct

Test #30:

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

input:

90 81
121.0826164250

output:

3
0.0000000000 0.0000000000
44.9997873845 40.5001913539
90.0000000000 81.0000000000

result:

ok correct

Test #31:

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

input:

34 99
3366.0000000000

output:

100
0.0000000000 0.0000000000
34.0000000000 0.0000000000
0.0000000000 1.0000000000
34.0000000000 1.0000000000
0.0000000000 2.0000000000
34.0000000000 2.0000000000
0.0000000000 3.0000000000
34.0000000000 3.0000000000
0.0000000000 4.0000000000
34.0000000000 4.0000000000
0.0000000000 5.0000000000
34.00...

result:

ok correct

Test #32:

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

input:

34 99
104.6756896330

output:

3
0.0000000000 0.0000000000
16.9998996426 49.5002922172
34.0000000000 99.0000000000

result:

ok correct

Test #33:

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

input:

3 3
5.9999

output:

3
0.0000000000 0.0000000000
0.0000500001 2.9999499999
3.0000000000 3.0000000000

result:

ok correct

Test #34:

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

input:

3 3
6.0

output:

3
0.0000000000 0.0000000000
0.0000000007 2.9999999993
3.0000000000 3.0000000000

result:

ok correct

Test #35:

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

input:

3 3
6.0001

output:

4
0.0000000000 0.0000000000
3.0000000000 0.0000000000
2.9884528506 1.0000000000
3.0000000000 3.0000000000

result:

ok correct

Test #36:

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

input:

4 4
13.999998

output:

5
0.0000000000 0.0000000000
4.0000000000 0.0000000000
0.0000000000 1.0000000000
0.7280442934 3.4539667800
4.0000000000 4.0000000000

result:

ok correct

Test #37:

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

input:

4 4
14.0

output:

5
0.0000000000 0.0000000000
4.0000000000 0.0000000000
0.0000000000 1.0000000000
0.7280427520 3.4539679360
4.0000000000 4.0000000000

result:

ok correct

Test #38:

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

input:

4 4
14.000002

output:

5
0.0000000000 0.0000000000
4.0000000000 0.0000000000
0.0000000000 1.0000000000
0.7280412107 3.4539690920
4.0000000000 4.0000000000

result:

ok correct

Test #39:

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

input:

4 4
15.123104

output:

5
0.0000000000 0.0000000000
4.0000000000 0.0000000000
0.0000000000 1.0000000000
0.0000009290 3.9999993033
4.0000000000 4.0000000000

result:

ok correct

Test #40:

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

input:

4 4
15.123106

output:

5
0.0000000000 0.0000000000
4.0000000000 0.0000000000
0.0000000000 1.0000000000
0.0000000005 3.9999999997
4.0000000000 4.0000000000

result:

ok correct

Test #41:

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

input:

4 4
15.123108

output:

5
0.0000000000 0.0000000000
4.0000000000 0.0000000000
0.0000000000 1.0000000000
0.0000000005 3.9999999997
4.0000000000 4.0000000000

result:

ok correct

Test #42:

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

input:

4 4
14.593385

output:

5
0.0000000000 0.0000000000
4.0000000000 0.0000000000
0.0000000000 1.0000000000
0.3174850359 3.7618862231
4.0000000000 4.0000000000

result:

ok correct

Test #43:

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

input:

4 4
14.593387

output:

5
0.0000000000 0.0000000000
4.0000000000 0.0000000000
0.0000000000 1.0000000000
0.3174837711 3.7618871717
4.0000000000 4.0000000000

result:

ok correct

Test #44:

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

input:

4 4
14.593389

output:

5
0.0000000000 0.0000000000
4.0000000000 0.0000000000
0.0000000000 1.0000000000
0.3174825055 3.7618881209
4.0000000000 4.0000000000

result:

ok correct

Test #45:

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

input:

2 2
4.0

output:

3
0.0000000000 0.0000000000
0.0000000005 1.9999999995
2.0000000000 2.0000000000

result:

ok correct

Test #46:

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

input:

3 3
5.0

output:

3
0.0000000000 0.0000000000
0.5645856529 2.4354143471
3.0000000000 3.0000000000

result:

ok correct

Test #47:

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

input:

4 4
15.123

output:

5
0.0000000000 0.0000000000
4.0000000000 0.0000000000
0.0000000000 1.0000000000
0.0000603576 3.9999547318
4.0000000000 4.0000000000

result:

ok correct

Test #48:

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

input:

4 4
14.1

output:

5
0.0000000000 0.0000000000
4.0000000000 0.0000000000
0.0000000000 1.0000000000
0.6526609673 3.5105042745
4.0000000000 4.0000000000

result:

ok correct

Test #49:

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

input:

3 3
9.0

output:

4
0.0000000000 0.0000000000
3.0000000000 0.0000000000
0.4382623087 1.0000000000
3.0000000000 3.0000000000

result:

ok correct

Test #50:

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

input:

4 4
16.0

output:

6
0.0000000000 0.0000000000
4.0000000000 0.0000000000
0.0000000000 1.0000000000
4.0000000000 1.0000000000
2.8137137750 2.0000000000
4.0000000000 4.0000000000

result:

ok correct