QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#32804#2290. Kinking CablesRobeZH#AC ✓3ms3868kbC++1.5kb2022-05-24 05:01:472022-05-24 05:01:50

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-24 05:01:50]
  • 评测
  • 测评结果:AC
  • 用时:3ms
  • 内存:3868kb
  • [2022-05-24 05:01:47]
  • 提交

answer

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

#define rep(i,n) for(int i=1;i<=n;++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define pb push_back
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef long double ld;
typedef long long ll;
const ld eps=1e-12;
struct P{
    ld x,y;
    P operator+(P p){return (P){x+p.x,y+p.y};}
    P operator*(ld c){return (P){x*c,y*c};}
    P operator-(P p){return (P){x-p.x,y-p.y};}
    ld dis(){return hypot(x,y);}
};
int n,m;
ld d;
vector<P> ans;
void sol(){
    P p=(P){0,0},T=(P){1.L*n,1.L*m};
    for(int i=0;i<=n;++i){
        int stp;
        if(i&1)stp=-1;else stp=1;
        for(int j=0;j<=1;++j){
            P nxt=p;
            if(j==0)nxt.y+=stp*m;
            else nxt.x+=1;
            if((p-nxt).dis()+(nxt-T).dis()>d+eps){
                ans.pb(p);
                ld l=0,r=1;
                rep(tim,256){
                    ld mid=(l+r)/2;
                    P pos=p*(1-mid)+nxt*mid;
                    if((p-pos).dis()+(pos-T).dis()>d)r=mid;else l=mid;
                }
                P pos=p*(1-l)+nxt*l;
                if((p-pos).dis()>eps)ans.pb(pos);
                ans.pb(T);
                return;
            }else{
                ans.pb(p);
                d-=(p-nxt).dis();
                p=nxt;

            }
        }
    }
}
int main() {
    scanf("%d%d%Lf",&n,&m,&d);
    sol();
    printf("%d\n",ans.size());
    for(P p:ans)printf("%.15Lf %.15Lf\n",p.x,p.y);
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

79 78
1980.7712136406

output:

49
0.000000000000000 0.000000000000000
0.000000000000000 78.000000000000000
1.000000000000000 78.000000000000000
1.000000000000000 0.000000000000000
2.000000000000000 0.000000000000000
2.000000000000000 78.000000000000000
3.000000000000000 78.000000000000000
3.000000000000000 0.000000000000000
4.000...

result:

ok correct

Test #2:

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

input:

33 65
1947.7601065763

output:

61
0.000000000000000 0.000000000000000
0.000000000000000 65.000000000000000
1.000000000000000 65.000000000000000
1.000000000000000 0.000000000000000
2.000000000000000 0.000000000000000
2.000000000000000 65.000000000000000
3.000000000000000 65.000000000000000
3.000000000000000 0.000000000000000
4.000...

result:

ok correct

Test #3:

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

input:

51 51
555.0803652025

output:

21
0.000000000000000 0.000000000000000
0.000000000000000 51.000000000000000
1.000000000000000 51.000000000000000
1.000000000000000 0.000000000000000
2.000000000000000 0.000000000000000
2.000000000000000 51.000000000000000
3.000000000000000 51.000000000000000
3.000000000000000 0.000000000000000
4.000...

result:

ok correct

Test #4:

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

input:

49 2
67.3588717350

output:

21
0.000000000000000 0.000000000000000
0.000000000000000 2.000000000000000
1.000000000000000 2.000000000000000
1.000000000000000 0.000000000000000
2.000000000000000 0.000000000000000
2.000000000000000 2.000000000000000
3.000000000000000 2.000000000000000
3.000000000000000 0.000000000000000
4.0000000...

result:

ok correct

Test #5:

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

input:

37 48
1713.3643608504

output:

70
0.000000000000000 0.000000000000000
0.000000000000000 48.000000000000000
1.000000000000000 48.000000000000000
1.000000000000000 0.000000000000000
2.000000000000000 0.000000000000000
2.000000000000000 48.000000000000000
3.000000000000000 48.000000000000000
3.000000000000000 0.000000000000000
4.000...

result:

ok correct

Test #6:

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

input:

51 79
820.1218304546

output:

21
0.000000000000000 0.000000000000000
0.000000000000000 79.000000000000000
1.000000000000000 79.000000000000000
1.000000000000000 0.000000000000000
2.000000000000000 0.000000000000000
2.000000000000000 79.000000000000000
3.000000000000000 79.000000000000000
3.000000000000000 0.000000000000000
4.000...

result:

ok correct

Test #7:

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

input:

6 8
37.5338494218

output:

9
0.000000000000000 0.000000000000000
0.000000000000000 8.000000000000000
1.000000000000000 8.000000000000000
1.000000000000000 0.000000000000000
2.000000000000000 0.000000000000000
2.000000000000000 8.000000000000000
3.000000000000000 8.000000000000000
3.000000000000000 3.160269548274349
6.00000000...

result:

ok correct

Test #8:

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

input:

5 5
7.1908428511

output:

3
0.000000000000000 0.000000000000000
0.000000000000000 0.389854732930364
5.000000000000000 5.000000000000000

result:

ok correct

Test #9:

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

input:

5 4
8.3927665498

output:

3
0.000000000000000 0.000000000000000
0.000000000000000 3.350796135613229
5.000000000000000 4.000000000000000

result:

ok correct

Test #10:

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

input:

4 2
6.4617533647

output:

5
0.000000000000000 0.000000000000000
0.000000000000000 2.000000000000000
1.000000000000000 2.000000000000000
1.000000000000000 1.569042614584077
4.000000000000000 2.000000000000000

result:

ok correct

Test #11:

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

input:

91 87
4830.8473359767

output:

109
0.000000000000000 0.000000000000000
0.000000000000000 87.000000000000000
1.000000000000000 87.000000000000000
1.000000000000000 0.000000000000000
2.000000000000000 0.000000000000000
2.000000000000000 87.000000000000000
3.000000000000000 87.000000000000000
3.000000000000000 0.000000000000000
4.00...

result:

ok correct

Test #12:

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

input:

90 90
5088.9280941138

output:

113
0.000000000000000 0.000000000000000
0.000000000000000 90.000000000000000
1.000000000000000 90.000000000000000
1.000000000000000 0.000000000000000
2.000000000000000 0.000000000000000
2.000000000000000 90.000000000000000
3.000000000000000 90.000000000000000
3.000000000000000 0.000000000000000
4.00...

result:

ok correct

Test #13:

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

input:

90 92
7004.0153432299

output:

153
0.000000000000000 0.000000000000000
0.000000000000000 92.000000000000000
1.000000000000000 92.000000000000000
1.000000000000000 0.000000000000000
2.000000000000000 0.000000000000000
2.000000000000000 92.000000000000000
3.000000000000000 92.000000000000000
3.000000000000000 0.000000000000000
4.00...

result:

ok correct

Test #14:

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

input:

91 83
1879.3819547895

output:

45
0.000000000000000 0.000000000000000
0.000000000000000 83.000000000000000
1.000000000000000 83.000000000000000
1.000000000000000 0.000000000000000
2.000000000000000 0.000000000000000
2.000000000000000 83.000000000000000
3.000000000000000 83.000000000000000
3.000000000000000 0.000000000000000
4.000...

result:

ok correct

Test #15:

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

input:

3 81
199.2077743610

output:

5
0.000000000000000 0.000000000000000
0.000000000000000 81.000000000000000
1.000000000000000 81.000000000000000
1.000000000000000 22.413176534009585
3.000000000000000 81.000000000000000

result:

ok correct

Test #16:

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

input:

4 89
288.5915130114

output:

9
0.000000000000000 0.000000000000000
0.000000000000000 89.000000000000000
1.000000000000000 89.000000000000000
1.000000000000000 0.000000000000000
2.000000000000000 0.000000000000000
2.000000000000000 89.000000000000000
3.000000000000000 89.000000000000000
3.000000000000000 79.731137486181855
4.000...

result:

ok correct

Test #17:

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

input:

95 3
175.9210001082

output:

55
0.000000000000000 0.000000000000000
0.000000000000000 3.000000000000000
1.000000000000000 3.000000000000000
1.000000000000000 0.000000000000000
2.000000000000000 0.000000000000000
2.000000000000000 3.000000000000000
3.000000000000000 3.000000000000000
3.000000000000000 0.000000000000000
4.0000000...

result:

ok correct

Test #18:

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

input:

84 4
310.3037172015

output:

115
0.000000000000000 0.000000000000000
0.000000000000000 4.000000000000000
1.000000000000000 4.000000000000000
1.000000000000000 0.000000000000000
2.000000000000000 0.000000000000000
2.000000000000000 4.000000000000000
3.000000000000000 4.000000000000000
3.000000000000000 0.000000000000000
4.000000...

result:

ok correct

Test #19:

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

input:

2 2
2.8284271248

output:

3
0.000000000000000 0.000000000000000
0.000000000000000 0.000000000183718
2.000000000000000 2.000000000000000

result:

ok correct

Test #20:

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

input:

100 100
10000.0000000000

output:

200
0.000000000000000 0.000000000000000
0.000000000000000 100.000000000000000
1.000000000000000 100.000000000000000
1.000000000000000 0.000000000000000
2.000000000000000 0.000000000000000
2.000000000000000 100.000000000000000
3.000000000000000 100.000000000000000
3.000000000000000 0.000000000000000
...

result:

ok correct

Test #21:

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

input:

100 100
9999.2500000000

output:

199
0.000000000000000 0.000000000000000
0.000000000000000 100.000000000000000
1.000000000000000 100.000000000000000
1.000000000000000 0.000000000000000
2.000000000000000 0.000000000000000
2.000000000000000 100.000000000000000
3.000000000000000 100.000000000000000
3.000000000000000 0.000000000000000
...

result:

ok correct

Test #22:

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

input:

100 100
2723.8981892905

output:

53
0.000000000000000 0.000000000000000
0.000000000000000 100.000000000000000
1.000000000000000 100.000000000000000
1.000000000000000 0.000000000000000
2.000000000000000 0.000000000000000
2.000000000000000 100.000000000000000
3.000000000000000 100.000000000000000
3.000000000000000 0.000000000000000
4...

result:

ok correct

Test #23:

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

input:

100 100
8994.4904261819

output:

179
0.000000000000000 0.000000000000000
0.000000000000000 100.000000000000000
1.000000000000000 100.000000000000000
1.000000000000000 0.000000000000000
2.000000000000000 0.000000000000000
2.000000000000000 100.000000000000000
3.000000000000000 100.000000000000000
3.000000000000000 0.000000000000000
...

result:

ok correct

Test #24:

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

input:

100 100
881.4998747190

output:

17
0.000000000000000 0.000000000000000
0.000000000000000 100.000000000000000
1.000000000000000 100.000000000000000
1.000000000000000 0.000000000000000
2.000000000000000 0.000000000000000
2.000000000000000 100.000000000000000
3.000000000000000 100.000000000000000
3.000000000000000 0.000000000000000
4...

result:

ok correct

Test #25:

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

input:

88 94
8266.2500000000

output:

177
0.000000000000000 0.000000000000000
0.000000000000000 94.000000000000000
1.000000000000000 94.000000000000000
1.000000000000000 0.000000000000000
2.000000000000000 0.000000000000000
2.000000000000000 94.000000000000000
3.000000000000000 94.000000000000000
3.000000000000000 0.000000000000000
4.00...

result:

ok correct

Test #26:

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

input:

75 37
2772.0000000000

output:

145
0.000000000000000 0.000000000000000
0.000000000000000 37.000000000000000
1.000000000000000 37.000000000000000
1.000000000000000 0.000000000000000
2.000000000000000 0.000000000000000
2.000000000000000 37.000000000000000
3.000000000000000 37.000000000000000
3.000000000000000 0.000000000000000
4.00...

result:

ok correct

Test #27:

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

input:

48 39
62.0000000000

output:

3
0.000000000000000 0.000000000000000
0.000000000000000 0.413043478260870
48.000000000000000 39.000000000000000

result:

ok correct

Test #28:

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

input:

98 94
135.9000000000

output:

3
0.000000000000000 0.000000000000000
0.000000000000000 0.343794749403341
98.000000000000000 94.000000000000000

result:

ok correct

Test #29:

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

input:

90 81
7290.0000000000

output:

177
0.000000000000000 0.000000000000000
0.000000000000000 81.000000000000000
1.000000000000000 81.000000000000000
1.000000000000000 0.000000000000000
2.000000000000000 0.000000000000000
2.000000000000000 81.000000000000000
3.000000000000000 81.000000000000000
3.000000000000000 0.000000000000000
4.00...

result:

ok correct

Test #30:

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

input:

90 81
121.0826164250

output:

3
0.000000000000000 0.000000000000000
0.000000000000000 0.000000004037658
90.000000000000000 81.000000000000000

result:

ok correct

Test #31:

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

input:

34 99
3366.0000000000

output:

69
0.000000000000000 0.000000000000000
0.000000000000000 99.000000000000000
1.000000000000000 99.000000000000000
1.000000000000000 0.000000000000000
2.000000000000000 0.000000000000000
2.000000000000000 99.000000000000000
3.000000000000000 99.000000000000000
3.000000000000000 0.000000000000000
4.000...

result:

ok correct

Test #32:

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

input:

34 99
104.6756896330

output:

3
0.000000000000000 0.000000000000000
0.000000000000000 0.000000012698340
34.000000000000000 99.000000000000000

result:

ok correct

Test #33:

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

input:

3 3
5.9999

output:

3
0.000000000000000 0.000000000000000
0.000000000000000 2.999899998333278
3.000000000000000 3.000000000000000

result:

ok correct

Test #34:

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

input:

3 3
6.0

output:

4
0.000000000000000 0.000000000000000
0.000000000000000 3.000000000000000
1.000000000000000 3.000000000000000
3.000000000000000 3.000000000000000

result:

ok correct

Test #35:

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

input:

3 3
6.0001

output:

5
0.000000000000000 0.000000000000000
0.000000000000000 3.000000000000000
1.000000000000000 3.000000000000000
1.000000000000000 2.999900002499875
3.000000000000000 3.000000000000000

result:

ok correct

Test #36:

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

input:

4 4
13.999998

output:

5
0.000000000000000 0.000000000000000
0.000000000000000 4.000000000000000
1.000000000000000 4.000000000000000
1.000000000000000 0.000001111111136
4.000000000000000 4.000000000000000

result:

ok correct

Test #37:

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

input:

4 4
14.0

output:

5
0.000000000000000 0.000000000000000
0.000000000000000 4.000000000000000
1.000000000000000 4.000000000000000
1.000000000000000 0.000000000000000
4.000000000000000 4.000000000000000

result:

ok correct

Test #38:

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

input:

4 4
14.000002

output:

6
0.000000000000000 0.000000000000000
0.000000000000000 4.000000000000000
1.000000000000000 4.000000000000000
1.000000000000000 0.000000000000000
1.000004999996000 0.000000000000000
4.000000000000000 4.000000000000000

result:

ok correct

Test #39:

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

input:

4 4
15.123104

output:

7
0.000000000000000 0.000000000000000
0.000000000000000 4.000000000000000
1.000000000000000 4.000000000000000
1.000000000000000 0.000000000000000
2.000000000000000 0.000000000000000
2.000000000000000 2.780773016041257
4.000000000000000 4.000000000000000

result:

ok correct

Test #40:

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

input:

4 4
15.123106

output:

7
0.000000000000000 0.000000000000000
0.000000000000000 4.000000000000000
1.000000000000000 4.000000000000000
1.000000000000000 0.000000000000000
2.000000000000000 0.000000000000000
2.000000000000000 2.780777187209400
4.000000000000000 4.000000000000000

result:

ok correct

Test #41:

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

input:

4 4
15.123108

output:

7
0.000000000000000 0.000000000000000
0.000000000000000 4.000000000000000
1.000000000000000 4.000000000000000
1.000000000000000 0.000000000000000
2.000000000000000 0.000000000000000
2.000000000000000 2.780781358366248
4.000000000000000 4.000000000000000

result:

ok correct

Test #42:

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

input:

4 4
14.593385

output:

7
0.000000000000000 0.000000000000000
0.000000000000000 4.000000000000000
1.000000000000000 4.000000000000000
1.000000000000000 0.000000000000000
2.000000000000000 0.000000000000000
2.000000000000000 0.926199481133665
4.000000000000000 4.000000000000000

result:

ok correct

Test #43:

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

input:

4 4
14.593387

output:

7
0.000000000000000 0.000000000000000
0.000000000000000 4.000000000000000
1.000000000000000 4.000000000000000
1.000000000000000 0.000000000000000
2.000000000000000 0.000000000000000
2.000000000000000 0.926211841318566
4.000000000000000 4.000000000000000

result:

ok correct

Test #44:

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

input:

4 4
14.593389

output:

7
0.000000000000000 0.000000000000000
0.000000000000000 4.000000000000000
1.000000000000000 4.000000000000000
1.000000000000000 0.000000000000000
2.000000000000000 0.000000000000000
2.000000000000000 0.926224201426889
4.000000000000000 4.000000000000000

result:

ok correct

Test #45:

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

input:

2 2
4.0

output:

4
0.000000000000000 0.000000000000000
0.000000000000000 2.000000000000000
1.000000000000000 2.000000000000000
2.000000000000000 2.000000000000000

result:

ok correct

Test #46:

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

input:

3 3
5.0

output:

3
0.000000000000000 0.000000000000000
0.000000000000000 1.750000000000000
3.000000000000000 3.000000000000000

result:

ok correct

Test #47:

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

input:

4 4
15.123

output:

7
0.000000000000000 0.000000000000000
0.000000000000000 4.000000000000000
1.000000000000000 4.000000000000000
1.000000000000000 0.000000000000000
2.000000000000000 0.000000000000000
2.000000000000000 2.780556099732858
4.000000000000000 4.000000000000000

result:

ok correct

Test #48:

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

input:

4 4
14.1

output:

6
0.000000000000000 0.000000000000000
0.000000000000000 4.000000000000000
1.000000000000000 4.000000000000000
1.000000000000000 0.000000000000000
1.240476190476190 0.000000000000000
4.000000000000000 4.000000000000000

result:

ok correct

Test #49:

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

input:

3 3
9.0

output:

5
0.000000000000000 0.000000000000000
0.000000000000000 3.000000000000000
1.000000000000000 3.000000000000000
1.000000000000000 0.900000000000000
3.000000000000000 3.000000000000000

result:

ok correct

Test #50:

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

input:

4 4
16.0

output:

8
0.000000000000000 0.000000000000000
0.000000000000000 4.000000000000000
1.000000000000000 4.000000000000000
1.000000000000000 0.000000000000000
2.000000000000000 0.000000000000000
2.000000000000000 4.000000000000000
3.000000000000000 4.000000000000000
4.000000000000000 4.000000000000000

result:

ok correct