QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#56582#2290. Kinking CableszghtyarecrenjWA 2ms3932kbC++171.5kb2022-10-20 11:18:312022-10-20 11:18:33

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-10-20 11:18:33]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:3932kb
  • [2022-10-20 11:18:31]
  • 提交

answer

#include <bits/stdc++.h>

typedef double db;
typedef long double ld;
const ld eps = 1e-12;

inline ld dist(ld x1, ld y1, ld x2, ld y2) {
    return sqrt((x2 - x1) * (x2 - x1) + (y2 - y1) * (y2 - y1));
}

inline ld dist(std::pair<ld, ld> x, std::pair<ld, ld> y) {
    return dist(x.first, x.second, y.first, y.second);
}

int n, m;
ld t;
std::vector<std::pair<ld, ld>> v;

int main() {
    scanf("%d%d%Lf", &n, &m, &t);
    std::pair<ld, ld> des(n, m), add(-1, -1);
    for (int i = 0; i <= n; ++i)
        v.emplace_back(i, 0), v.emplace_back(i, m);
    int fin = 0;
    for (int i = 1; i < v.size(); ++i) {
        if (dist(v[i], v[i - 1]) + dist(v[i], des) > t + eps) {
            fin = i;
            ld l = 0, r = 1;
            for (int j = 0; j < 256; ++j) {
                ld mid = (l + r) / 2.0;
                std::pair<ld, ld> cur(v[i - 1].first * (1 - mid) + v[i].first * mid, v[i - 1].second * (1 - mid) + v[i].second * mid);
                if (dist(v[i - 1], cur) + dist(cur, des) > t) r = mid; else l = mid;
            }
            std::pair<ld, ld> cur(v[i - 1].first * (1 - l) + v[i].first * l, v[i - 1].second * (1 - l) + v[i].second * l);
            if (dist(cur, v[i - 1]) > eps) add = cur;
            break;
        }
        t -= dist(v[i], v[i - 1]);
    }
    printf("%d\n", fin + (add.first != -1) + 1);
    for (int i = 0; i < fin; ++i) printf("%.10Lf %.10Lf\n", v[i].first, v[i].second);
    if (add.first != -1) printf("%.10Lf %.10Lf\n", add.first, add.second);
    printf("%d %d\n", n, m);
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

79 78
1980.7712136406

output:

27
0.0000000000 0.0000000000
0.0000000000 78.0000000000
1.0000000000 0.0000000000
1.0000000000 78.0000000000
2.0000000000 0.0000000000
2.0000000000 78.0000000000
3.0000000000 0.0000000000
3.0000000000 78.0000000000
4.0000000000 0.0000000000
4.0000000000 78.0000000000
5.0000000000 0.0000000000
5.0000...

result:

ok correct

Test #2:

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

input:

33 65
1947.7601065763

output:

32
0.0000000000 0.0000000000
0.0000000000 65.0000000000
1.0000000000 0.0000000000
1.0000000000 65.0000000000
2.0000000000 0.0000000000
2.0000000000 65.0000000000
3.0000000000 0.0000000000
3.0000000000 65.0000000000
4.0000000000 0.0000000000
4.0000000000 65.0000000000
5.0000000000 0.0000000000
5.0000...

result:

ok correct

Test #3:

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

input:

51 51
555.0803652025

output:

12
0.0000000000 0.0000000000
0.0000000000 51.0000000000
1.0000000000 0.0000000000
1.0000000000 51.0000000000
2.0000000000 0.0000000000
2.0000000000 51.0000000000
3.0000000000 0.0000000000
3.0000000000 51.0000000000
4.0000000000 0.0000000000
4.0000000000 51.0000000000
4.7228817859 14.1330289215
51 51

result:

ok correct

Test #4:

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

input:

49 2
67.3588717350

output:

14
0.0000000000 0.0000000000
0.0000000000 2.0000000000
1.0000000000 0.0000000000
1.0000000000 2.0000000000
2.0000000000 0.0000000000
2.0000000000 2.0000000000
3.0000000000 0.0000000000
3.0000000000 2.0000000000
4.0000000000 0.0000000000
4.0000000000 2.0000000000
5.0000000000 0.0000000000
5.000000000...

result:

ok correct

Test #5:

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

input:

37 48
1713.3643608504

output:

38
0.0000000000 0.0000000000
0.0000000000 48.0000000000
1.0000000000 0.0000000000
1.0000000000 48.0000000000
2.0000000000 0.0000000000
2.0000000000 48.0000000000
3.0000000000 0.0000000000
3.0000000000 48.0000000000
4.0000000000 0.0000000000
4.0000000000 48.0000000000
5.0000000000 0.0000000000
5.0000...

result:

ok correct

Test #6:

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

input:

51 79
820.1218304546

output:

12
0.0000000000 0.0000000000
0.0000000000 79.0000000000
1.0000000000 0.0000000000
1.0000000000 79.0000000000
2.0000000000 0.0000000000
2.0000000000 79.0000000000
3.0000000000 0.0000000000
3.0000000000 79.0000000000
4.0000000000 0.0000000000
4.0000000000 79.0000000000
4.5653694146 34.3358162464
51 79

result:

ok correct

Test #7:

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

input:

6 8
37.5338494218

output:

6
0.0000000000 0.0000000000
0.0000000000 8.0000000000
1.0000000000 0.0000000000
1.0000000000 8.0000000000
1.7551471905 1.9588224758
6 8

result:

ok correct

Test #8:

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

input:

5 5
7.1908428511

output:

3
0.0000000000 0.0000000000
0.0000000000 0.3898547329
5 5

result:

ok correct

Test #9:

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

input:

5 4
8.3927665498

output:

3
0.0000000000 0.0000000000
0.0000000000 3.3507961356
5 4

result:

ok correct

Test #10:

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

input:

4 2
6.4617533647

output:

4
0.0000000000 0.0000000000
0.0000000000 2.0000000000
0.3268683630 1.3462632741
4 2

result:

ok correct

Test #11:

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

input:

91 87
4830.8473359767

output:

57
0.0000000000 0.0000000000
0.0000000000 87.0000000000
1.0000000000 0.0000000000
1.0000000000 87.0000000000
2.0000000000 0.0000000000
2.0000000000 87.0000000000
3.0000000000 0.0000000000
3.0000000000 87.0000000000
4.0000000000 0.0000000000
4.0000000000 87.0000000000
5.0000000000 0.0000000000
5.0000...

result:

ok correct

Test #12:

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

input:

90 90
5088.9280941138

output:

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

result:

ok correct

Test #13:

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

input:

90 92
7004.0153432299

output:

78
0.0000000000 0.0000000000
0.0000000000 92.0000000000
1.0000000000 0.0000000000
1.0000000000 92.0000000000
2.0000000000 0.0000000000
2.0000000000 92.0000000000
3.0000000000 0.0000000000
3.0000000000 92.0000000000
4.0000000000 0.0000000000
4.0000000000 92.0000000000
5.0000000000 0.0000000000
5.0000...

result:

ok correct

Test #14:

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

input:

91 83
1879.3819547895

output:

24
0.0000000000 0.0000000000
0.0000000000 83.0000000000
1.0000000000 0.0000000000
1.0000000000 83.0000000000
2.0000000000 0.0000000000
2.0000000000 83.0000000000
3.0000000000 0.0000000000
3.0000000000 83.0000000000
4.0000000000 0.0000000000
4.0000000000 83.0000000000
5.0000000000 0.0000000000
5.0000...

result:

ok correct

Test #15:

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

input:

3 81
199.2077743610

output:

4
0.0000000000 0.0000000000
0.0000000000 81.0000000000
0.7293805854 21.9201725793
3 81

result:

ok correct

Test #16:

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

input:

4 89
288.5915130114

output:

6
0.0000000000 0.0000000000
0.0000000000 89.0000000000
1.0000000000 0.0000000000
1.0000000000 89.0000000000
1.1191051936 78.3996377702
4 89

result:

ok correct

Test #17:

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

input:

95 3
175.9210001082

output:

34
0.0000000000 0.0000000000
0.0000000000 3.0000000000
1.0000000000 0.0000000000
1.0000000000 3.0000000000
2.0000000000 0.0000000000
2.0000000000 3.0000000000
3.0000000000 0.0000000000
3.0000000000 3.0000000000
4.0000000000 0.0000000000
4.0000000000 3.0000000000
5.0000000000 0.0000000000
5.000000000...

result:

ok correct

Test #18:

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

input:

84 4
310.3037172015

output:

66
0.0000000000 0.0000000000
0.0000000000 4.0000000000
1.0000000000 0.0000000000
1.0000000000 4.0000000000
2.0000000000 0.0000000000
2.0000000000 4.0000000000
3.0000000000 0.0000000000
3.0000000000 4.0000000000
4.0000000000 0.0000000000
4.0000000000 4.0000000000
5.0000000000 0.0000000000
5.000000000...

result:

ok correct

Test #19:

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

input:

2 2
2.8284271248

output:

3
0.0000000000 0.0000000000
0.0000000000 0.0000000002
2 2

result:

ok correct

Test #20:

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

input:

100 100
10000.0000000000

output:

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

result:

ok correct

Test #21:

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

input:

100 100
9999.2500000000

output:

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

result:

ok correct

Test #22:

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

input:

100 100
2723.8981892905

output:

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

result:

ok correct

Test #23:

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

input:

100 100
8994.4904261819

output:

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

result:

ok correct

Test #24:

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

input:

100 100
881.4998747190

output:

10
0.0000000000 0.0000000000
0.0000000000 100.0000000000
1.0000000000 0.0000000000
1.0000000000 100.0000000000
2.0000000000 0.0000000000
2.0000000000 100.0000000000
3.0000000000 0.0000000000
3.0000000000 100.0000000000
3.6516520385 34.8347961482
100 100

result:

ok correct

Test #25:

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

input:

88 94
8266.2500000000

output:

90
0.0000000000 0.0000000000
0.0000000000 94.0000000000
1.0000000000 0.0000000000
1.0000000000 94.0000000000
2.0000000000 0.0000000000
2.0000000000 94.0000000000
3.0000000000 0.0000000000
3.0000000000 94.0000000000
4.0000000000 0.0000000000
4.0000000000 94.0000000000
5.0000000000 0.0000000000
5.0000...

result:

ok correct

Test #26:

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

input:

75 37
2772.0000000000

output:

76
0.0000000000 0.0000000000
0.0000000000 37.0000000000
1.0000000000 0.0000000000
1.0000000000 37.0000000000
2.0000000000 0.0000000000
2.0000000000 37.0000000000
3.0000000000 0.0000000000
3.0000000000 37.0000000000
4.0000000000 0.0000000000
4.0000000000 37.0000000000
5.0000000000 0.0000000000
5.0000...

result:

ok correct

Test #27:

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

input:

48 39
62.0000000000

output:

3
0.0000000000 0.0000000000
0.0000000000 0.4130434783
48 39

result:

ok correct

Test #28:

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

input:

98 94
135.9000000000

output:

3
0.0000000000 0.0000000000
0.0000000000 0.3437947494
98 94

result:

ok correct

Test #29:

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

input:

90 81
7290.0000000000

output:

92
0.0000000000 0.0000000000
0.0000000000 81.0000000000
1.0000000000 0.0000000000
1.0000000000 81.0000000000
2.0000000000 0.0000000000
2.0000000000 81.0000000000
3.0000000000 0.0000000000
3.0000000000 81.0000000000
4.0000000000 0.0000000000
4.0000000000 81.0000000000
5.0000000000 0.0000000000
5.0000...

result:

ok correct

Test #30:

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

input:

90 81
121.0826164250

output:

3
0.0000000000 0.0000000000
0.0000000000 0.0000000040
90 81

result:

ok correct

Test #31:

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

input:

34 99
3366.0000000000

output:

36
0.0000000000 0.0000000000
0.0000000000 99.0000000000
1.0000000000 0.0000000000
1.0000000000 99.0000000000
2.0000000000 0.0000000000
2.0000000000 99.0000000000
3.0000000000 0.0000000000
3.0000000000 99.0000000000
4.0000000000 0.0000000000
4.0000000000 99.0000000000
5.0000000000 0.0000000000
5.0000...

result:

ok correct

Test #32:

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

input:

34 99
104.6756896330

output:

3
0.0000000000 0.0000000000
0.0000000000 0.0000000127
34 99

result:

ok correct

Test #33:

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

input:

3 3
5.9999

output:

3
0.0000000000 0.0000000000
0.0000000000 2.9998999983
3 3

result:

ok correct

Test #34:

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

input:

3 3
6.0

output:

3
0.0000000000 0.0000000000
0.0000000000 3.0000000000
3 3

result:

ok correct

Test #35:

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

input:

3 3
6.0001

output:

4
0.0000000000 0.0000000000
0.0000000000 3.0000000000
0.0000462460 2.9998612619
3 3

result:

ok correct

Test #36:

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

input:

4 4
13.999998

output:

5
0.0000000000 0.0000000000
0.0000000000 4.0000000000
1.0000000000 0.0000000000
1.0000000000 2.5408659842
4 4

result:

ok correct

Test #37:

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

input:

4 4
14.0

output:

5
0.0000000000 0.0000000000
0.0000000000 4.0000000000
1.0000000000 0.0000000000
1.0000000000 2.5408695390
4 4

result:

ok correct

Test #38:

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

input:

4 4
14.000002

output:

5
0.0000000000 0.0000000000
0.0000000000 4.0000000000
1.0000000000 0.0000000000
1.0000000000 2.5408730939
4 4

result:

ok correct

Test #39:

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

input:

4 4
15.123104

output:

5
0.0000000000 0.0000000000
0.0000000000 4.0000000000
1.0000000000 0.0000000000
1.0000000000 3.9999983744
4 4

result:

ok correct

Test #40:

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

input:

4 4
15.123106

output:

6
0.0000000000 0.0000000000
0.0000000000 4.0000000000
1.0000000000 0.0000000000
1.0000000000 4.0000000000
1.0000001199 3.9999995205
4 4

result:

ok correct

Test #41:

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

input:

4 4
15.123108

output:

6
0.0000000000 0.0000000000
0.0000000000 4.0000000000
1.0000000000 0.0000000000
1.0000000000 4.0000000000
1.0000007603 3.9999969589
4 4

result:

ok correct

Test #42:

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

input:

4 4
14.593385

output:

5
0.0000000000 0.0000000000
0.0000000000 4.0000000000
1.0000000000 0.0000000000
1.0000000000 3.4134833812
4 4

result:

ok correct

Test #43:

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

input:

4 4
14.593387

output:

5
0.0000000000 0.0000000000
0.0000000000 4.0000000000
1.0000000000 0.0000000000
1.0000000000 3.4134858560
4 4

result:

ok correct

Test #44:

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

input:

4 4
14.593389

output:

5
0.0000000000 0.0000000000
0.0000000000 4.0000000000
1.0000000000 0.0000000000
1.0000000000 3.4134883309
4 4

result:

ok correct

Test #45:

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

input:

2 2
4.0

output:

3
0.0000000000 0.0000000000
0.0000000000 2.0000000000
2 2

result:

ok correct

Test #46:

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

input:

3 3
5.0

output:

3
0.0000000000 0.0000000000
0.0000000000 1.7500000000
3 3

result:

ok correct

Test #47:

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

input:

4 4
15.123

output:

5
0.0000000000 0.0000000000
0.0000000000 4.0000000000
1.0000000000 0.0000000000
1.0000000000 3.9998943725
4 4

result:

ok correct

Test #48:

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

input:

4 4
14.1

output:

5
0.0000000000 0.0000000000
0.0000000000 4.0000000000
1.0000000000 0.0000000000
1.0000000000 2.7121495467
4 4

result:

ok correct

Test #49:

score: -100
Wrong Answer
time: 2ms
memory: 3768kb

input:

3 3
9.0

output:

4
0.0000000000 0.0000000000
0.0000000000 3.0000000000
0.8451409985 0.4645770045
3 3

result:

wrong answer Output path has non-consecutive points within distance 1 of each other: (0.000000000000,0.000000000000) and (0.845140998500,0.464577004500)lie too close to each other