QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#134387#2290. Kinking CablesPetroTarnavskyi#AC ✓3ms3836kbC++171.8kb2023-08-03 18:45:402023-08-03 18:45:43

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-08-03 18:45:43]
  • 评测
  • 测评结果:AC
  • 用时:3ms
  • 内存:3836kb
  • [2023-08-03 18:45:40]
  • 提交

answer

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

#define SZ(a) (int)a.size()
#define ALL(a) a.begin(), a.end()
#define FOR(i, a, b) for (int i = (a); i<(b); ++i)
#define RFOR(i, b, a) for (int i = (b)-1; i>=(a); --i)
#define MP make_pair
#define PB push_back
#define F first
#define S second
#define FILL(a, b) memset(a, b, sizeof(a))

typedef long long LL;
typedef pair<int, int> PII;
typedef vector<int> VI;
typedef long double db;

vector<pair<db, db>> ans;

const db eps = 1e-6;

int main()
{
	int n, m;
	db l;
	cin >> n >> m >> l;
	
	ans.PB(MP(n, m));
	while(true){
		assert(l >= sqrt(n * n + m * m) - eps);
		
		if(l <= n + m){
			db L = 0, R = m;
			FOR(t, 0, 300){
				db x = (L + R) / 2;
				db val = (m - x) + sqrt(x * x + n * n);
				if(val > l)
					L = x;
				else
					R = x;
			}
			ans.PB(MP(n, R));
			ans.PB(MP(0, 0));
			break;
		}
		l -= m + 1;
		
		ans.PB(MP(n, 0));
		ans.PB(MP(n - 1, 0));
		n--;
		
		if(l <= m + sqrt(n * n + m * m)){			
			db L = 0, R = m;
			FOR(t, 0, 300){
				db x = (L + R) / 2;
				db val = x + sqrt(x * x + n * n);
				if(val > l)
					R = x;
				else
					L = x;
			}
			ans.PB(MP(n, R));
			ans.PB(MP(0, 0));
			break;
		}
		l -= m;
		ans.PB(MP(n, m));
		
		
		if(l <= sqrt(m * m + (n - 1) * (n - 1)) + 1){
			db L = n - 1, R = n;
			FOR(t, 0, 300){
				db x = (L + R) / 2;
				db val = (n - x) + sqrt(x * x + m * m);
				
				if(val > l)
					L = x;
				else
					R = x;
			}
			ans.PB(MP(R, m));
			ans.PB(MP(0, 0));
			break;
			
			
		}
		l -= 1;
		ans.PB(MP(n - 1, m));
		n--;

		assert(n >= 0);
	}
	
	
	//cerr << sta << " " << cur << endl;
	
	
	
	cout << SZ(ans) << endl;
	reverse(ALL(ans));
	cout << fixed << setprecision(8);
	
	FOR(i, 0, SZ(ans))
		cout << ans[i].F << " " << ans[i].S << endl;
	

	
	
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

79 78
1980.7712136406

output:

49
0.00000000 0.00000000
56.00000000 72.31127465
56.00000000 0.00000000
57.00000000 0.00000000
57.00000000 78.00000000
58.00000000 78.00000000
58.00000000 0.00000000
59.00000000 0.00000000
59.00000000 78.00000000
60.00000000 78.00000000
60.00000000 0.00000000
61.00000000 0.00000000
61.00000000 78.00...

result:

ok correct

Test #2:

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

input:

33 65
1947.7601065763

output:

61
0.00000000 0.00000000
4.00000000 16.64308721
4.00000000 0.00000000
5.00000000 0.00000000
5.00000000 65.00000000
6.00000000 65.00000000
6.00000000 0.00000000
7.00000000 0.00000000
7.00000000 65.00000000
8.00000000 65.00000000
8.00000000 0.00000000
9.00000000 0.00000000
9.00000000 65.00000000
10.00...

result:

ok correct

Test #3:

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

input:

51 51
555.0803652025

output:

21
0.00000000 0.00000000
42.00000000 33.41160772
42.00000000 0.00000000
43.00000000 0.00000000
43.00000000 51.00000000
44.00000000 51.00000000
44.00000000 0.00000000
45.00000000 0.00000000
45.00000000 51.00000000
46.00000000 51.00000000
46.00000000 0.00000000
47.00000000 0.00000000
47.00000000 51.00...

result:

ok correct

Test #4:

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

input:

49 2
67.3588717350

output:

21
0.00000000 0.00000000
40.00000000 0.35727619
40.00000000 0.00000000
41.00000000 0.00000000
41.00000000 2.00000000
42.00000000 2.00000000
42.00000000 0.00000000
43.00000000 0.00000000
43.00000000 2.00000000
44.00000000 2.00000000
44.00000000 0.00000000
45.00000000 0.00000000
45.00000000 2.00000000...

result:

ok correct

Test #5:

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

input:

37 48
1713.3643608504

output:

70
0.00000000 0.00000000
3.78460864 48.00000000
4.00000000 48.00000000
4.00000000 0.00000000
5.00000000 0.00000000
5.00000000 48.00000000
6.00000000 48.00000000
6.00000000 0.00000000
7.00000000 0.00000000
7.00000000 48.00000000
8.00000000 48.00000000
8.00000000 0.00000000
9.00000000 0.00000000
9.000...

result:

ok correct

Test #6:

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

input:

51 79
820.1218304546

output:

21
0.00000000 0.00000000
42.00000000 41.25164760
42.00000000 0.00000000
43.00000000 0.00000000
43.00000000 79.00000000
44.00000000 79.00000000
44.00000000 0.00000000
45.00000000 0.00000000
45.00000000 79.00000000
46.00000000 79.00000000
46.00000000 0.00000000
47.00000000 0.00000000
47.00000000 79.00...

result:

ok correct

Test #7:

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

input:

6 8
37.5338494218

output:

9
0.00000000 0.00000000
3.00000000 4.83973045
3.00000000 0.00000000
4.00000000 0.00000000
4.00000000 8.00000000
5.00000000 8.00000000
5.00000000 0.00000000
6.00000000 0.00000000
6.00000000 8.00000000

result:

ok correct

Test #8:

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

input:

5 5
7.1908428511

output:

3
0.00000000 0.00000000
5.00000000 4.61014527
5.00000000 5.00000000

result:

ok correct

Test #9:

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

input:

5 4
8.3927665498

output:

3
0.00000000 0.00000000
5.00000000 0.64920386
5.00000000 4.00000000

result:

ok correct

Test #10:

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

input:

4 2
6.4617533647

output:

5
0.00000000 0.00000000
3.00000000 0.43095739
3.00000000 0.00000000
4.00000000 0.00000000
4.00000000 2.00000000

result:

ok correct

Test #11:

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

input:

91 87
4830.8473359767

output:

109
0.00000000 0.00000000
38.00000000 79.09635886
38.00000000 0.00000000
39.00000000 0.00000000
39.00000000 87.00000000
40.00000000 87.00000000
40.00000000 0.00000000
41.00000000 0.00000000
41.00000000 87.00000000
42.00000000 87.00000000
42.00000000 0.00000000
43.00000000 0.00000000
43.00000000 87.0...

result:

ok correct

Test #12:

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

input:

90 90
5088.9280941138

output:

113
0.00000000 0.00000000
35.00000000 34.66613321
35.00000000 0.00000000
36.00000000 0.00000000
36.00000000 90.00000000
37.00000000 90.00000000
37.00000000 0.00000000
38.00000000 0.00000000
38.00000000 90.00000000
39.00000000 90.00000000
39.00000000 0.00000000
40.00000000 0.00000000
40.00000000 90.0...

result:

ok correct

Test #13:

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

input:

90 92
7004.0153432299

output:

153
0.00000000 0.00000000
15.00000000 10.63041264
15.00000000 0.00000000
16.00000000 0.00000000
16.00000000 92.00000000
17.00000000 92.00000000
17.00000000 0.00000000
18.00000000 0.00000000
18.00000000 92.00000000
19.00000000 92.00000000
19.00000000 0.00000000
20.00000000 0.00000000
20.00000000 92.0...

result:

ok correct

Test #14:

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

input:

91 83
1879.3819547895

output:

45
0.00000000 0.00000000
70.00000000 36.45715444
70.00000000 0.00000000
71.00000000 0.00000000
71.00000000 83.00000000
72.00000000 83.00000000
72.00000000 0.00000000
73.00000000 0.00000000
73.00000000 83.00000000
74.00000000 83.00000000
74.00000000 0.00000000
75.00000000 0.00000000
75.00000000 83.00...

result:

ok correct

Test #15:

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

input:

3 81
199.2077743610

output:

5
0.00000000 0.00000000
2.00000000 58.58682347
2.00000000 0.00000000
3.00000000 0.00000000
3.00000000 81.00000000

result:

ok correct

Test #16:

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

input:

4 89
288.5915130114

output:

9
0.00000000 0.00000000
1.00000000 9.26886251
1.00000000 0.00000000
2.00000000 0.00000000
2.00000000 89.00000000
3.00000000 89.00000000
3.00000000 0.00000000
4.00000000 0.00000000
4.00000000 89.00000000

result:

ok correct

Test #17:

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

input:

95 3
175.9210001082

output:

55
0.00000000 0.00000000
69.00000000 0.07904517
69.00000000 3.00000000
70.00000000 3.00000000
70.00000000 0.00000000
71.00000000 0.00000000
71.00000000 3.00000000
72.00000000 3.00000000
72.00000000 0.00000000
73.00000000 0.00000000
73.00000000 3.00000000
74.00000000 3.00000000
74.00000000 0.00000000...

result:

ok correct

Test #18:

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

input:

84 4
310.3037172015

output:

115
0.00000000 0.00000000
28.00000000 1.75097802
28.00000000 4.00000000
29.00000000 4.00000000
29.00000000 0.00000000
30.00000000 0.00000000
30.00000000 4.00000000
31.00000000 4.00000000
31.00000000 0.00000000
32.00000000 0.00000000
32.00000000 4.00000000
33.00000000 4.00000000
33.00000000 0.0000000...

result:

ok correct

Test #19:

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

input:

2 2
2.8284271248

output:

3
0.00000000 0.00000000
2.00000000 2.00000000
2.00000000 2.00000000

result:

ok correct

Test #20:

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

input:

100 100
10000.0000000000

output:

199
0.00000000 0.00000000
2.00000000 0.00000000
2.00000000 100.00000000
3.00000000 100.00000000
3.00000000 0.00000000
4.00000000 0.00000000
4.00000000 100.00000000
5.00000000 100.00000000
5.00000000 0.00000000
6.00000000 0.00000000
6.00000000 100.00000000
7.00000000 100.00000000
7.00000000 0.0000000...

result:

ok correct

Test #21:

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

input:

100 100
9999.2500000000

output:

199
0.00000000 0.00000000
2.00000000 0.97500000
2.00000000 100.00000000
3.00000000 100.00000000
3.00000000 0.00000000
4.00000000 0.00000000
4.00000000 100.00000000
5.00000000 100.00000000
5.00000000 0.00000000
6.00000000 0.00000000
6.00000000 100.00000000
7.00000000 100.00000000
7.00000000 0.0000000...

result:

ok correct

Test #22:

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

input:

100 100
2723.8981892905

output:

53
0.00000000 0.00000000
75.00000000 85.30869442
75.00000000 0.00000000
76.00000000 0.00000000
76.00000000 100.00000000
77.00000000 100.00000000
77.00000000 0.00000000
78.00000000 0.00000000
78.00000000 100.00000000
79.00000000 100.00000000
79.00000000 0.00000000
80.00000000 0.00000000
80.00000000 1...

result:

ok correct

Test #23:

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

input:

100 100
8994.4904261819

output:

179
0.00000000 0.00000000
12.00000000 7.84804920
12.00000000 100.00000000
13.00000000 100.00000000
13.00000000 0.00000000
14.00000000 0.00000000
14.00000000 100.00000000
15.00000000 100.00000000
15.00000000 0.00000000
16.00000000 0.00000000
16.00000000 100.00000000
17.00000000 100.00000000
17.000000...

result:

ok correct

Test #24:

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

input:

100 100
881.4998747190

output:

17
0.00000000 0.00000000
93.00000000 62.46768461
93.00000000 0.00000000
94.00000000 0.00000000
94.00000000 100.00000000
95.00000000 100.00000000
95.00000000 0.00000000
96.00000000 0.00000000
96.00000000 100.00000000
97.00000000 100.00000000
97.00000000 0.00000000
98.00000000 0.00000000
98.00000000 1...

result:

ok correct

Test #25:

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

input:

88 94
8266.2500000000

output:

177
0.00000000 0.00000000
1.00000000 0.22500000
1.00000000 0.00000000
2.00000000 0.00000000
2.00000000 94.00000000
3.00000000 94.00000000
3.00000000 0.00000000
4.00000000 0.00000000
4.00000000 94.00000000
5.00000000 94.00000000
5.00000000 0.00000000
6.00000000 0.00000000
6.00000000 94.00000000
7.000...

result:

ok correct

Test #26:

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

input:

75 37
2772.0000000000

output:

145
0.00000000 0.00000000
4.00000000 36.89189189
4.00000000 0.00000000
5.00000000 0.00000000
5.00000000 37.00000000
6.00000000 37.00000000
6.00000000 0.00000000
7.00000000 0.00000000
7.00000000 37.00000000
8.00000000 37.00000000
8.00000000 0.00000000
9.00000000 0.00000000
9.00000000 37.00000000
10.0...

result:

ok correct

Test #27:

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

input:

48 39
62.0000000000

output:

3
0.00000000 0.00000000
48.00000000 38.58695652
48.00000000 39.00000000

result:

ok correct

Test #28:

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

input:

98 94
135.9000000000

output:

3
0.00000000 0.00000000
98.00000000 93.65620525
98.00000000 94.00000000

result:

ok correct

Test #29:

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

input:

90 81
7290.0000000000

output:

177
0.00000000 0.00000000
3.00000000 77.97115385
3.00000000 0.00000000
4.00000000 0.00000000
4.00000000 81.00000000
5.00000000 81.00000000
5.00000000 0.00000000
6.00000000 0.00000000
6.00000000 81.00000000
7.00000000 81.00000000
7.00000000 0.00000000
8.00000000 0.00000000
8.00000000 81.00000000
9.00...

result:

ok correct

Test #30:

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

input:

90 81
121.0826164250

output:

3
0.00000000 0.00000000
90.00000000 81.00000000
90.00000000 81.00000000

result:

ok correct

Test #31:

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

input:

34 99
3366.0000000000

output:

69
0.00000000 0.00000000
1.00000000 32.99242424
1.00000000 0.00000000
2.00000000 0.00000000
2.00000000 99.00000000
3.00000000 99.00000000
3.00000000 0.00000000
4.00000000 0.00000000
4.00000000 99.00000000
5.00000000 99.00000000
5.00000000 0.00000000
6.00000000 0.00000000
6.00000000 99.00000000
7.000...

result:

ok correct

Test #32:

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

input:

34 99
104.6756896330

output:

3
0.00000000 0.00000000
34.00000000 98.99999999
34.00000000 99.00000000

result:

ok correct

Test #33:

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

input:

3 3
5.9999

output:

3
0.00000000 0.00000000
3.00000000 0.00010000
3.00000000 3.00000000

result:

ok correct

Test #34:

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

input:

3 3
6.0

output:

3
0.00000000 0.00000000
3.00000000 0.00000000
3.00000000 3.00000000

result:

ok correct

Test #35:

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

input:

3 3
6.0001

output:

5
0.00000000 0.00000000
2.00000000 0.00010000
2.00000000 0.00000000
3.00000000 0.00000000
3.00000000 3.00000000

result:

ok correct

Test #36:

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

input:

4 4
13.999998

output:

5
0.00000000 0.00000000
3.00000000 3.99999889
3.00000000 0.00000000
4.00000000 0.00000000
4.00000000 4.00000000

result:

ok correct

Test #37:

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

input:

4 4
14.0

output:

5
0.00000000 0.00000000
3.00000000 4.00000000
3.00000000 0.00000000
4.00000000 0.00000000
4.00000000 4.00000000

result:

ok correct

Test #38:

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

input:

4 4
14.000002

output:

6
0.00000000 0.00000000
2.99999500 4.00000000
3.00000000 4.00000000
3.00000000 0.00000000
4.00000000 0.00000000
4.00000000 4.00000000

result:

ok correct

Test #39:

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

input:

4 4
15.123104

output:

7
0.00000000 0.00000000
2.00000000 1.21922698
2.00000000 4.00000000
3.00000000 4.00000000
3.00000000 0.00000000
4.00000000 0.00000000
4.00000000 4.00000000

result:

ok correct

Test #40:

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

input:

4 4
15.123106

output:

7
0.00000000 0.00000000
2.00000000 1.21922281
2.00000000 4.00000000
3.00000000 4.00000000
3.00000000 0.00000000
4.00000000 0.00000000
4.00000000 4.00000000

result:

ok correct

Test #41:

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

input:

4 4
15.123108

output:

7
0.00000000 0.00000000
2.00000000 1.21921864
2.00000000 4.00000000
3.00000000 4.00000000
3.00000000 0.00000000
4.00000000 0.00000000
4.00000000 4.00000000

result:

ok correct

Test #42:

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

input:

4 4
14.593385

output:

7
0.00000000 0.00000000
2.00000000 3.07380052
2.00000000 4.00000000
3.00000000 4.00000000
3.00000000 0.00000000
4.00000000 0.00000000
4.00000000 4.00000000

result:

ok correct

Test #43:

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

input:

4 4
14.593387

output:

7
0.00000000 0.00000000
2.00000000 3.07378816
2.00000000 4.00000000
3.00000000 4.00000000
3.00000000 0.00000000
4.00000000 0.00000000
4.00000000 4.00000000

result:

ok correct

Test #44:

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

input:

4 4
14.593389

output:

7
0.00000000 0.00000000
2.00000000 3.07377580
2.00000000 4.00000000
3.00000000 4.00000000
3.00000000 0.00000000
4.00000000 0.00000000
4.00000000 4.00000000

result:

ok correct

Test #45:

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

input:

2 2
4.0

output:

3
0.00000000 0.00000000
2.00000000 0.00000000
2.00000000 2.00000000

result:

ok correct

Test #46:

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

input:

3 3
5.0

output:

3
0.00000000 0.00000000
3.00000000 1.25000000
3.00000000 3.00000000

result:

ok correct

Test #47:

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

input:

4 4
15.123

output:

7
0.00000000 0.00000000
2.00000000 1.21944390
2.00000000 4.00000000
3.00000000 4.00000000
3.00000000 0.00000000
4.00000000 0.00000000
4.00000000 4.00000000

result:

ok correct

Test #48:

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

input:

4 4
14.1

output:

6
0.00000000 0.00000000
2.75952381 4.00000000
3.00000000 4.00000000
3.00000000 0.00000000
4.00000000 0.00000000
4.00000000 4.00000000

result:

ok correct

Test #49:

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

input:

3 3
9.0

output:

5
0.00000000 0.00000000
2.00000000 2.10000000
2.00000000 0.00000000
3.00000000 0.00000000
3.00000000 3.00000000

result:

ok correct

Test #50:

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

input:

4 4
16.0

output:

7
0.00000000 0.00000000
2.00000000 0.00000000
2.00000000 4.00000000
3.00000000 4.00000000
3.00000000 0.00000000
4.00000000 0.00000000
4.00000000 4.00000000

result:

ok correct