QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#122528#2290. Kinking Cablesbatrr#AC ✓2ms3808kbC++171.8kb2023-07-10 17:58:492023-07-10 17:58:51

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-07-10 17:58:51]
  • 评测
  • 测评结果:AC
  • 用时:2ms
  • 内存:3808kb
  • [2023-07-10 17:58:49]
  • 提交

answer

#include <bits/stdc++.h>

#define f first
#define s second
#define pb push_back
#define mp make_pair

using namespace std;

typedef long long ll;
using ld = long double;
typedef pair<int, int> pii;
typedef pair<long long, long long> pll;

const int N = 305, K = 30, inf = 1e9, mod = 998244353;
const ll INF = 1e18;

#define X first
#define Y second

ld dist(ld x, ld y, ld x2, ld y2)
{
    return sqrt(abs(x-x2)*abs(x-x2)+abs(y-y2)*abs(y-y2));
}

void solve() {
    int x = 0, y = 0;
    vector<pair<ld,ld>> A;
    int n, m;
    cin >> n >> m;
    ld L;
    cin >> L;
    A.push_back({0,0});
    while (true)
    {
        int x2 = x, y2 = y;
        if (x%2==0 and y==0) y2 = m;
        if (x%2==0 and y==m) x2++;
        if (x%2==1 and y==0) x2++;
        if (x%2==1 and y==m) y2 = 0;
        ld D = dist(x,y,x2,y2)+dist(x2,y2,n,m);
        if (L>D)
        {
            L -= dist(x,y,x2,y2);
            x = x2, y = y2;
            A.push_back({x,y});
            continue;
        }
        ld l = 0, r = 1;
        for (int w=0;w<60;w++)
        {
            ld M = (l+r)/2;
            ld x3 = x2*M+x*(1-M), y3 = y2*M+y*(1-M);
            D = dist(x,y,x3,y3)+dist(x3,y3,n,m);
            if (D<L) l = M;
            else r = M;
        }
        ld x3 = x2*l+x*(1-l), y3 = y2*l+y*(1-l);
        A.push_back({x3,y3});
        A.push_back({n,m});
        break;
    }
    cout.precision(20);
    cout << A.size() << "\n";
    for (int i=0;i<A.size();i++)
    {
        cout << A[i].X << " " << A[i].Y << "\n";
    }
}


int main() {
#ifdef DEBUG
    freopen("input.txt", "r", stdin);
#endif
    ios_base::sync_with_stdio(false);
    int t = 1;
//    cin >> t;
    for (int i = 1; i <= t; i++) {
//        cout << "Case #" << i << endl;
        solve();
    }
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

79 78
1980.7712136406

output:

49
0 0
0 78
1 78
1 0
2 0
2 78
3 78
3 0
4 0
4 78
5 78
5 0
6 0
6 78
7 78
7 0
8 0
8 78
9 78
9 0
10 0
10 78
11 78
11 0
12 0
12 78
13 78
13 0
14 0
14 78
15 78
15 0
16 0
16 78
17 78
17 0
18 0
18 78
19 78
19 0
20 0
20 78
21 78
21 0
22 0
22 78
23 78
23 5.6887253541016319872
79 78

result:

ok correct

Test #2:

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

input:

33 65
1947.7601065763

output:

61
0 0
0 65
1 65
1 0
2 0
2 65
3 65
3 0
4 0
4 65
5 65
5 0
6 0
6 65
7 65
7 0
8 0
8 65
9 65
9 0
10 0
10 65
11 65
11 0
12 0
12 65
13 65
13 0
14 0
14 65
15 65
15 0
16 0
16 65
17 65
17 0
18 0
18 65
19 65
19 0
20 0
20 65
21 65
21 0
22 0
22 65
23 65
23 0
24 0
24 65
25 65
25 0
26 0
26 65
27 65
27 0
28 0
28 6...

result:

ok correct

Test #3:

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

input:

51 51
555.0803652025

output:

21
0 0
0 51
1 51
1 0
2 0
2 51
3 51
3 0
4 0
4 51
5 51
5 0
6 0
6 51
7 51
7 0
8 0
8 51
9 51
9 17.588392284132756342
51 51

result:

ok correct

Test #4:

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

input:

49 2
67.3588717350

output:

21
0 0
0 2
1 2
1 0
2 0
2 2
3 2
3 0
4 0
4 2
5 2
5 0
6 0
6 2
7 2
7 0
8 0
8 2
9 2
9 1.6427238116127441635
49 2

result:

ok correct

Test #5:

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

input:

37 48
1713.3643608504

output:

70
0 0
0 48
1 48
1 0
2 0
2 48
3 48
3 0
4 0
4 48
5 48
5 0
6 0
6 48
7 48
7 0
8 0
8 48
9 48
9 0
10 0
10 48
11 48
11 0
12 0
12 48
13 48
13 0
14 0
14 48
15 48
15 0
16 0
16 48
17 48
17 0
18 0
18 48
19 48
19 0
20 0
20 48
21 48
21 0
22 0
22 48
23 48
23 0
24 0
24 48
25 48
25 0
26 0
26 48
27 48
27 0
28 0
28 4...

result:

ok correct

Test #6:

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

input:

51 79
820.1218304546

output:

21
0 0
0 79
1 79
1 0
2 0
2 79
3 79
3 0
4 0
4 79
5 79
5 0
6 0
6 79
7 79
7 0
8 0
8 79
9 79
9 37.748352401900414493
51 79

result:

ok correct

Test #7:

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

input:

6 8
37.5338494218

output:

9
0 0
0 8
1 8
1 0
2 0
2 8
3 8
3 3.1602695482743494229
6 8

result:

ok correct

Test #8:

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

input:

5 5
7.1908428511

output:

3
0 0
0 0.38985473293036429845
5 5

result:

ok correct

Test #9:

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

input:

5 4
8.3927665498

output:

3
0 0
0 3.3507961356132292437
5 4

result:

ok correct

Test #10:

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

input:

4 2
6.4617533647

output:

5
0 0
0 2
1 2
1 1.5690426145840771603
4 2

result:

ok correct

Test #11:

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

input:

91 87
4830.8473359767

output:

109
0 0
0 87
1 87
1 0
2 0
2 87
3 87
3 0
4 0
4 87
5 87
5 0
6 0
6 87
7 87
7 0
8 0
8 87
9 87
9 0
10 0
10 87
11 87
11 0
12 0
12 87
13 87
13 0
14 0
14 87
15 87
15 0
16 0
16 87
17 87
17 0
18 0
18 87
19 87
19 0
20 0
20 87
21 87
21 0
22 0
22 87
23 87
23 0
24 0
24 87
25 87
25 0
26 0
26 87
27 87
27 0
28 0
28 ...

result:

ok correct

Test #12:

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

input:

90 90
5088.9280941138

output:

113
0 0
0 90
1 90
1 0
2 0
2 90
3 90
3 0
4 0
4 90
5 90
5 0
6 0
6 90
7 90
7 0
8 0
8 90
9 90
9 0
10 0
10 90
11 90
11 0
12 0
12 90
13 90
13 0
14 0
14 90
15 90
15 0
16 0
16 90
17 90
17 0
18 0
18 90
19 90
19 0
20 0
20 90
21 90
21 0
22 0
22 90
23 90
23 0
24 0
24 90
25 90
25 0
26 0
26 90
27 90
27 0
28 0
28 ...

result:

ok correct

Test #13:

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

input:

90 92
7004.0153432299

output:

153
0 0
0 92
1 92
1 0
2 0
2 92
3 92
3 0
4 0
4 92
5 92
5 0
6 0
6 92
7 92
7 0
8 0
8 92
9 92
9 0
10 0
10 92
11 92
11 0
12 0
12 92
13 92
13 0
14 0
14 92
15 92
15 0
16 0
16 92
17 92
17 0
18 0
18 92
19 92
19 0
20 0
20 92
21 92
21 0
22 0
22 92
23 92
23 0
24 0
24 92
25 92
25 0
26 0
26 92
27 92
27 0
28 0
28 ...

result:

ok correct

Test #14:

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

input:

91 83
1879.3819547895

output:

45
0 0
0 83
1 83
1 0
2 0
2 83
3 83
3 0
4 0
4 83
5 83
5 0
6 0
6 83
7 83
7 0
8 0
8 83
9 83
9 0
10 0
10 83
11 83
11 0
12 0
12 83
13 83
13 0
14 0
14 83
15 83
15 0
16 0
16 83
17 83
17 0
18 0
18 83
19 83
19 0
20 0
20 83
21 83
21 46.542845558498796461
91 83

result:

ok correct

Test #15:

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

input:

3 81
199.2077743610

output:

5
0 0
0 81
1 81
1 22.413176534009585391
3 81

result:

ok correct

Test #16:

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

input:

4 89
288.5915130114

output:

9
0 0
0 89
1 89
1 0
2 0
2 89
3 89
3 79.73113748618185543
4 89

result:

ok correct

Test #17:

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

input:

95 3
175.9210001082

output:

55
0 0
0 3
1 3
1 0
2 0
2 3
3 3
3 0
4 0
4 3
5 3
5 0
6 0
6 3
7 3
7 0
8 0
8 3
9 3
9 0
10 0
10 3
11 3
11 0
12 0
12 3
13 3
13 0
14 0
14 3
15 3
15 0
16 0
16 3
17 3
17 0
18 0
18 3
19 3
19 0
20 0
20 3
21 3
21 0
22 0
22 3
23 3
23 0
24 0
24 3
25 3
25 0
26 0
26 2.9209548318481289098
95 3

result:

ok correct

Test #18:

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

input:

84 4
310.3037172015

output:

115
0 0
0 4
1 4
1 0
2 0
2 4
3 4
3 0
4 0
4 4
5 4
5 0
6 0
6 4
7 4
7 0
8 0
8 4
9 4
9 0
10 0
10 4
11 4
11 0
12 0
12 4
13 4
13 0
14 0
14 4
15 4
15 0
16 0
16 4
17 4
17 0
18 0
18 4
19 4
19 0
20 0
20 4
21 4
21 0
22 0
22 4
23 4
23 0
24 0
24 4
25 4
25 0
26 0
26 4
27 4
27 0
28 0
28 4
29 4
29 0
30 0
30 4
31 4
3...

result:

ok correct

Test #19:

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

input:

2 2
2.8284271248

output:

3
0 0
0 1.8371849701270814847e-10
2 2

result:

ok correct

Test #20:

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

input:

100 100
10000.0000000000

output:

199
0 0
0 100
1 100
1 0
2 0
2 100
3 100
3 0
4 0
4 100
5 100
5 0
6 0
6 100
7 100
7 0
8 0
8 100
9 100
9 0
10 0
10 100
11 100
11 0
12 0
12 100
13 100
13 0
14 0
14 100
15 100
15 0
16 0
16 100
17 100
17 0
18 0
18 100
19 100
19 0
20 0
20 100
21 100
21 0
22 0
22 100
23 100
23 0
24 0
24 100
25 100
25 0
26 0...

result:

ok correct

Test #21:

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

input:

100 100
9999.2500000000

output:

199
0 0
0 100
1 100
1 0
2 0
2 100
3 100
3 0
4 0
4 100
5 100
5 0
6 0
6 100
7 100
7 0
8 0
8 100
9 100
9 0
10 0
10 100
11 100
11 0
12 0
12 100
13 100
13 0
14 0
14 100
15 100
15 0
16 0
16 100
17 100
17 0
18 0
18 100
19 100
19 0
20 0
20 100
21 100
21 0
22 0
22 100
23 100
23 0
24 0
24 100
25 100
25 0
26 0...

result:

ok correct

Test #22:

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

input:

100 100
2723.8981892905

output:

53
0 0
0 100
1 100
1 0
2 0
2 100
3 100
3 0
4 0
4 100
5 100
5 0
6 0
6 100
7 100
7 0
8 0
8 100
9 100
9 0
10 0
10 100
11 100
11 0
12 0
12 100
13 100
13 0
14 0
14 100
15 100
15 0
16 0
16 100
17 100
17 0
18 0
18 100
19 100
19 0
20 0
20 100
21 100
21 0
22 0
22 100
23 100
23 0
24 0
24 100
25 100
25 14.6913...

result:

ok correct

Test #23:

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

input:

100 100
8994.4904261819

output:

179
0 0
0 100
1 100
1 0
2 0
2 100
3 100
3 0
4 0
4 100
5 100
5 0
6 0
6 100
7 100
7 0
8 0
8 100
9 100
9 0
10 0
10 100
11 100
11 0
12 0
12 100
13 100
13 0
14 0
14 100
15 100
15 0
16 0
16 100
17 100
17 0
18 0
18 100
19 100
19 0
20 0
20 100
21 100
21 0
22 0
22 100
23 100
23 0
24 0
24 100
25 100
25 0
26 0...

result:

ok correct

Test #24:

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

input:

100 100
881.4998747190

output:

17
0 0
0 100
1 100
1 0
2 0
2 100
3 100
3 0
4 0
4 100
5 100
5 0
6 0
6 100
7 100
7 37.532315389757344923
100 100

result:

ok correct

Test #25:

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

input:

88 94
8266.2500000000

output:

177
0 0
0 94
1 94
1 0
2 0
2 94
3 94
3 0
4 0
4 94
5 94
5 0
6 0
6 94
7 94
7 0
8 0
8 94
9 94
9 0
10 0
10 94
11 94
11 0
12 0
12 94
13 94
13 0
14 0
14 94
15 94
15 0
16 0
16 94
17 94
17 0
18 0
18 94
19 94
19 0
20 0
20 94
21 94
21 0
22 0
22 94
23 94
23 0
24 0
24 94
25 94
25 0
26 0
26 94
27 94
27 0
28 0
28 ...

result:

ok correct

Test #26:

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

input:

75 37
2772.0000000000

output:

145
0 0
0 37
1 37
1 0
2 0
2 37
3 37
3 0
4 0
4 37
5 37
5 0
6 0
6 37
7 37
7 0
8 0
8 37
9 37
9 0
10 0
10 37
11 37
11 0
12 0
12 37
13 37
13 0
14 0
14 37
15 37
15 0
16 0
16 37
17 37
17 0
18 0
18 37
19 37
19 0
20 0
20 37
21 37
21 0
22 0
22 37
23 37
23 0
24 0
24 37
25 37
25 0
26 0
26 37
27 37
27 0
28 0
28 ...

result:

ok correct

Test #27:

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

input:

48 39
62.0000000000

output:

3
0 0
0 0.41304347826086954942
48 39

result:

ok correct

Test #28:

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

input:

98 94
135.9000000000

output:

3
0 0
0 0.34379474940334120783
98 94

result:

ok correct

Test #29:

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

input:

90 81
7290.0000000000

output:

177
0 0
0 81
1 81
1 0
2 0
2 81
3 81
3 0
4 0
4 81
5 81
5 0
6 0
6 81
7 81
7 0
8 0
8 81
9 81
9 0
10 0
10 81
11 81
11 0
12 0
12 81
13 81
13 0
14 0
14 81
15 81
15 0
16 0
16 81
17 81
17 0
18 0
18 81
19 81
19 0
20 0
20 81
21 81
21 0
22 0
22 81
23 81
23 0
24 0
24 81
25 81
25 0
26 0
26 81
27 81
27 0
28 0
28 ...

result:

ok correct

Test #30:

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

input:

90 81
121.0826164250

output:

3
0 0
0 4.0376577784342893018e-09
90 81

result:

ok correct

Test #31:

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

input:

34 99
3366.0000000000

output:

69
0 0
0 99
1 99
1 0
2 0
2 99
3 99
3 0
4 0
4 99
5 99
5 0
6 0
6 99
7 99
7 0
8 0
8 99
9 99
9 0
10 0
10 99
11 99
11 0
12 0
12 99
13 99
13 0
14 0
14 99
15 99
15 0
16 0
16 99
17 99
17 0
18 0
18 99
19 99
19 0
20 0
20 99
21 99
21 0
22 0
22 99
23 99
23 0
24 0
24 99
25 99
25 0
26 0
26 99
27 99
27 0
28 0
28 9...

result:

ok correct

Test #32:

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

input:

34 99
104.6756896330

output:

3
0 0
0 1.2698339949858417075e-08
34 99

result:

ok correct

Test #33:

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

input:

3 3
5.9999

output:

3
0 0
0 2.9998999983332777742
3 3

result:

ok correct

Test #34:

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

input:

3 3
6.0

output:

3
0 0
0 2.9999999999999999974
3 3

result:

ok correct

Test #35:

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

input:

3 3
6.0001

output:

5
0 0
0 3
1 3
1 2.9999000024998750081
3 3

result:

ok correct

Test #36:

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

input:

4 4
13.999998

output:

5
0 0
0 4
1 4
1 1.1111111358035052898e-06
4 4

result:

ok correct

Test #37:

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

input:

4 4
14.0

output:

5
0 0
0 4
1 4
1 3.4694469519536141888e-18
4 4

result:

ok correct

Test #38:

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

input:

4 4
14.000002

output:

6
0 0
0 4
1 4
1 0
1.0000049999960000041 0
4 4

result:

ok correct

Test #39:

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

input:

4 4
15.123104

output:

7
0 0
0 4
1 4
1 0
2 0
2 2.7807730160412570848
4 4

result:

ok correct

Test #40:

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

input:

4 4
15.123106

output:

7
0 0
0 4
1 4
1 0
2 0
2 2.7807771872093996444
4 4

result:

ok correct

Test #41:

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

input:

4 4
15.123108

output:

7
0 0
0 4
1 4
1 0
2 0
2 2.7807813583662479469
4 4

result:

ok correct

Test #42:

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

input:

4 4
14.593385

output:

7
0 0
0 4
1 4
1 0
2 0
2 0.92619948113366532341
4 4

result:

ok correct

Test #43:

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

input:

4 4
14.593387

output:

7
0 0
0 4
1 4
1 0
2 0
2 0.92621184131856612934
4 4

result:

ok correct

Test #44:

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

input:

4 4
14.593389

output:

7
0 0
0 4
1 4
1 0
2 0
2 0.92622420142688859437
4 4

result:

ok correct

Test #45:

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

input:

2 2
4.0

output:

3
0 0
0 1.9999999999999999983
2 2

result:

ok correct

Test #46:

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

input:

3 3
5.0

output:

3
0 0
0 1.7499999999999999991
3 3

result:

ok correct

Test #47:

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

input:

4 4
15.123

output:

7
0 0
0 4
1 4
1 0
2 0
2 2.7805560997328584126
4 4

result:

ok correct

Test #48:

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

input:

4 4
14.1

output:

6
0 0
0 4
1 4
1 0
1.2404761904761904762 0
4 4

result:

ok correct

Test #49:

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

input:

3 3
9.0

output:

5
0 0
0 3
1 3
1 0.90000000000000000052
3 3

result:

ok correct

Test #50:

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

input:

4 4
16.0

output:

7
0 0
0 4
1 4
1 0
2 0
2 3.9999999999999999965
4 4

result:

ok correct