QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#134438#2290. Kinking CablesYarema#AC ✓1ms3848kbC++171.8kb2023-08-03 19:45:312023-08-03 19:45:33

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 19:45:33]
  • 评测
  • 测评结果:AC
  • 用时:1ms
  • 内存:3848kb
  • [2023-08-03 19:45:31]
  • 提交

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;

const int INF = 1e9 + 7;
const double EPS = 1e-6;

struct point
{
	double x, y;
	
	point() {}
	point(double a, double b): x(a), y(b) {};
	point operator +(const point& p) const
	{
		return point(x + p.x, y + p.y);
	}
	point operator -(const point& p) const
	{
		return point(x - p.x, y - p.y);
	}
	point operator *(double d) const
	{
		return point(x * d, y * d);
	}
	double d2()
	{
		return sqrt(x * x + y * y);
	}
};

double dis(point a, point b)
{
	a = a - b;
	return a.d2();
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	int n, m;
	cin >> n >> m;
	double l;
	cin >> l;
	vector<point> ans;
	int j = 0;
	point a(0, 0);
	ans.PB(a);
	point b(n, 0);
	point c(0, 1);
	point d(n, m);
	while (dis(a, b) + dis(b, c) + dis(c, d) < l)
	{
		ans.PB(b);
		ans.PB(c);
		a.y += 1;
		b.y += 1;
		c.y += 1;
		l -= dis(a, b) + dis(b, c);
		j++;
	}
	assert(l + EPS > dis(a, d));
	double L = 0, R = 1;
	point v1(n, 0);
	point v2(-n, 0);
	FOR (i, 0, 100)
	{
		double M = (L + R) / 2;
		b = a + v1 * M;
		c = d + v2 * M;
		double ds = dis(a, b) + dis(b, c) + dis(c, d);
		if (ds < l)
			L = M;
		else
			R = M;
	}
	ans.PB(a + v1 * L);
	ans.PB(d + v2 * L);
	ans.PB(d);
	cout << fixed << setprecision(7) << SZ(ans) << '\n';
	for (auto p : ans)
		cout << p.x << ' ' << p.y << '\n';
	
	
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

79 78
1980.7712136406

output:

26
0.0000000 0.0000000
79.0000000 0.0000000
0.0000000 1.0000000
79.0000000 1.0000000
0.0000000 2.0000000
79.0000000 2.0000000
0.0000000 3.0000000
79.0000000 3.0000000
0.0000000 4.0000000
79.0000000 4.0000000
0.0000000 5.0000000
79.0000000 5.0000000
0.0000000 6.0000000
79.0000000 6.0000000
0.0000000 ...

result:

ok correct

Test #2:

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

input:

33 65
1947.7601065763

output:

60
0.0000000 0.0000000
33.0000000 0.0000000
0.0000000 1.0000000
33.0000000 1.0000000
0.0000000 2.0000000
33.0000000 2.0000000
0.0000000 3.0000000
33.0000000 3.0000000
0.0000000 4.0000000
33.0000000 4.0000000
0.0000000 5.0000000
33.0000000 5.0000000
0.0000000 6.0000000
33.0000000 6.0000000
0.0000000 ...

result:

ok correct

Test #3:

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

input:

51 51
555.0803652025

output:

12
0.0000000 0.0000000
51.0000000 0.0000000
0.0000000 1.0000000
51.0000000 1.0000000
0.0000000 2.0000000
51.0000000 2.0000000
0.0000000 3.0000000
51.0000000 3.0000000
0.0000000 4.0000000
43.7601491 4.0000000
7.2398509 51.0000000
51.0000000 51.0000000

result:

ok correct

Test #4:

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

input:

49 2
67.3588717350

output:

4
0.0000000 0.0000000
29.0352484 0.0000000
19.9647516 2.0000000
49.0000000 2.0000000

result:

ok correct

Test #5:

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

input:

37 48
1713.3643608504

output:

48
0.0000000 0.0000000
37.0000000 0.0000000
0.0000000 1.0000000
37.0000000 1.0000000
0.0000000 2.0000000
37.0000000 2.0000000
0.0000000 3.0000000
37.0000000 3.0000000
0.0000000 4.0000000
37.0000000 4.0000000
0.0000000 5.0000000
37.0000000 5.0000000
0.0000000 6.0000000
37.0000000 6.0000000
0.0000000 ...

result:

ok correct

Test #6:

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

input:

51 79
820.1218304546

output:

18
0.0000000 0.0000000
51.0000000 0.0000000
0.0000000 1.0000000
51.0000000 1.0000000
0.0000000 2.0000000
51.0000000 2.0000000
0.0000000 3.0000000
51.0000000 3.0000000
0.0000000 4.0000000
51.0000000 4.0000000
0.0000000 5.0000000
51.0000000 5.0000000
0.0000000 6.0000000
51.0000000 6.0000000
0.0000000 ...

result:

ok correct

Test #7:

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

input:

6 8
37.5338494218

output:

8
0.0000000 0.0000000
6.0000000 0.0000000
0.0000000 1.0000000
6.0000000 1.0000000
0.0000000 2.0000000
3.6206365 2.0000000
2.3793635 8.0000000
6.0000000 8.0000000

result:

ok correct

Test #8:

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

input:

5 5
7.1908428511

output:

4
0.0000000 0.0000000
0.1949274 0.0000000
4.8050726 5.0000000
5.0000000 5.0000000

result:

ok correct

Test #9:

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

input:

5 4
8.3927665498

output:

4
0.0000000 0.0000000
2.1692128 0.0000000
2.8307872 4.0000000
5.0000000 4.0000000

result:

ok correct

Test #10:

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

input:

4 2
6.4617533647

output:

4
0.0000000 0.0000000
2.2092238 0.0000000
1.7907762 2.0000000
4.0000000 2.0000000

result:

ok correct

Test #11:

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

input:

91 87
4830.8473359767

output:

54
0.0000000 0.0000000
91.0000000 0.0000000
0.0000000 1.0000000
91.0000000 1.0000000
0.0000000 2.0000000
91.0000000 2.0000000
0.0000000 3.0000000
91.0000000 3.0000000
0.0000000 4.0000000
91.0000000 4.0000000
0.0000000 5.0000000
91.0000000 5.0000000
0.0000000 6.0000000
91.0000000 6.0000000
0.0000000 ...

result:

ok correct

Test #12:

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

input:

90 90
5088.9280941138

output:

58
0.0000000 0.0000000
90.0000000 0.0000000
0.0000000 1.0000000
90.0000000 1.0000000
0.0000000 2.0000000
90.0000000 2.0000000
0.0000000 3.0000000
90.0000000 3.0000000
0.0000000 4.0000000
90.0000000 4.0000000
0.0000000 5.0000000
90.0000000 5.0000000
0.0000000 6.0000000
90.0000000 6.0000000
0.0000000 ...

result:

ok correct

Test #13:

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

input:

90 92
7004.0153432299

output:

80
0.0000000 0.0000000
90.0000000 0.0000000
0.0000000 1.0000000
90.0000000 1.0000000
0.0000000 2.0000000
90.0000000 2.0000000
0.0000000 3.0000000
90.0000000 3.0000000
0.0000000 4.0000000
90.0000000 4.0000000
0.0000000 5.0000000
90.0000000 5.0000000
0.0000000 6.0000000
90.0000000 6.0000000
0.0000000 ...

result:

ok correct

Test #14:

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

input:

91 83
1879.3819547895

output:

22
0.0000000 0.0000000
91.0000000 0.0000000
0.0000000 1.0000000
91.0000000 1.0000000
0.0000000 2.0000000
91.0000000 2.0000000
0.0000000 3.0000000
91.0000000 3.0000000
0.0000000 4.0000000
91.0000000 4.0000000
0.0000000 5.0000000
91.0000000 5.0000000
0.0000000 6.0000000
91.0000000 6.0000000
0.0000000 ...

result:

ok correct

Test #15:

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

input:

3 81
199.2077743610

output:

48
0.0000000 0.0000000
3.0000000 0.0000000
0.0000000 1.0000000
3.0000000 1.0000000
0.0000000 2.0000000
3.0000000 2.0000000
0.0000000 3.0000000
3.0000000 3.0000000
0.0000000 4.0000000
3.0000000 4.0000000
0.0000000 5.0000000
3.0000000 5.0000000
0.0000000 6.0000000
3.0000000 6.0000000
0.0000000 7.00000...

result:

ok correct

Test #16:

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

input:

4 89
288.5915130114

output:

60
0.0000000 0.0000000
4.0000000 0.0000000
0.0000000 1.0000000
4.0000000 1.0000000
0.0000000 2.0000000
4.0000000 2.0000000
0.0000000 3.0000000
4.0000000 3.0000000
0.0000000 4.0000000
4.0000000 4.0000000
0.0000000 5.0000000
4.0000000 5.0000000
0.0000000 6.0000000
4.0000000 6.0000000
0.0000000 7.00000...

result:

ok correct

Test #17:

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

input:

95 3
175.9210001082

output:

4
0.0000000 0.0000000
67.7024451 0.0000000
27.2975549 3.0000000
95.0000000 3.0000000

result:

ok correct

Test #18:

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

input:

84 4
310.3037172015

output:

6
0.0000000 0.0000000
84.0000000 0.0000000
0.0000000 1.0000000
56.5358463 1.0000000
27.4641537 4.0000000
84.0000000 4.0000000

result:

ok correct

Test #19:

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

input:

2 2
2.8284271248

output:

4
0.0000000 0.0000000
0.0000000 0.0000000
2.0000000 2.0000000
2.0000000 2.0000000

result:

ok correct

Test #20:

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

input:

100 100
10000.0000000000

output:

102
0.0000000 0.0000000
100.0000000 0.0000000
0.0000000 1.0000000
100.0000000 1.0000000
0.0000000 2.0000000
100.0000000 2.0000000
0.0000000 3.0000000
100.0000000 3.0000000
0.0000000 4.0000000
100.0000000 4.0000000
0.0000000 5.0000000
100.0000000 5.0000000
0.0000000 6.0000000
100.0000000 6.0000000
0....

result:

ok correct

Test #21:

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

input:

100 100
9999.2500000000

output:

102
0.0000000 0.0000000
100.0000000 0.0000000
0.0000000 1.0000000
100.0000000 1.0000000
0.0000000 2.0000000
100.0000000 2.0000000
0.0000000 3.0000000
100.0000000 3.0000000
0.0000000 4.0000000
100.0000000 4.0000000
0.0000000 5.0000000
100.0000000 5.0000000
0.0000000 6.0000000
100.0000000 6.0000000
0....

result:

ok correct

Test #22:

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

input:

100 100
2723.8981892905

output:

28
0.0000000 0.0000000
100.0000000 0.0000000
0.0000000 1.0000000
100.0000000 1.0000000
0.0000000 2.0000000
100.0000000 2.0000000
0.0000000 3.0000000
100.0000000 3.0000000
0.0000000 4.0000000
100.0000000 4.0000000
0.0000000 5.0000000
100.0000000 5.0000000
0.0000000 6.0000000
100.0000000 6.0000000
0.0...

result:

ok correct

Test #23:

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

input:

100 100
8994.4904261819

output:

92
0.0000000 0.0000000
100.0000000 0.0000000
0.0000000 1.0000000
100.0000000 1.0000000
0.0000000 2.0000000
100.0000000 2.0000000
0.0000000 3.0000000
100.0000000 3.0000000
0.0000000 4.0000000
100.0000000 4.0000000
0.0000000 5.0000000
100.0000000 5.0000000
0.0000000 6.0000000
100.0000000 6.0000000
0.0...

result:

ok correct

Test #24:

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

input:

100 100
881.4998747190

output:

10
0.0000000 0.0000000
100.0000000 0.0000000
0.0000000 1.0000000
100.0000000 1.0000000
0.0000000 2.0000000
100.0000000 2.0000000
0.0000000 3.0000000
82.4100836 3.0000000
17.5899164 100.0000000
100.0000000 100.0000000

result:

ok correct

Test #25:

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

input:

88 94
8266.2500000000

output:

96
0.0000000 0.0000000
88.0000000 0.0000000
0.0000000 1.0000000
88.0000000 1.0000000
0.0000000 2.0000000
88.0000000 2.0000000
0.0000000 3.0000000
88.0000000 3.0000000
0.0000000 4.0000000
88.0000000 4.0000000
0.0000000 5.0000000
88.0000000 5.0000000
0.0000000 6.0000000
88.0000000 6.0000000
0.0000000 ...

result:

ok correct

Test #26:

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

input:

75 37
2772.0000000000

output:

38
0.0000000 0.0000000
75.0000000 0.0000000
0.0000000 1.0000000
75.0000000 1.0000000
0.0000000 2.0000000
75.0000000 2.0000000
0.0000000 3.0000000
75.0000000 3.0000000
0.0000000 4.0000000
75.0000000 4.0000000
0.0000000 5.0000000
75.0000000 5.0000000
0.0000000 6.0000000
75.0000000 6.0000000
0.0000000 ...

result:

ok correct

Test #27:

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

input:

48 39
62.0000000000

output:

4
0.0000000 0.0000000
0.3392857 0.0000000
47.6607143 39.0000000
48.0000000 39.0000000

result:

ok correct

Test #28:

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

input:

98 94
135.9000000000

output:

4
0.0000000 0.0000000
0.1900396 0.0000000
97.8099604 94.0000000
98.0000000 94.0000000

result:

ok correct

Test #29:

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

input:

90 81
7290.0000000000

output:

82
0.0000000 0.0000000
90.0000000 0.0000000
0.0000000 1.0000000
90.0000000 1.0000000
0.0000000 2.0000000
90.0000000 2.0000000
0.0000000 3.0000000
90.0000000 3.0000000
0.0000000 4.0000000
90.0000000 4.0000000
0.0000000 5.0000000
90.0000000 5.0000000
0.0000000 6.0000000
90.0000000 6.0000000
0.0000000 ...

result:

ok correct

Test #30:

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

input:

90 81
121.0826164250

output:

4
0.0000000 0.0000000
0.0000000 0.0000000
90.0000000 81.0000000
90.0000000 81.0000000

result:

ok correct

Test #31:

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

input:

34 99
3366.0000000000

output:

100
0.0000000 0.0000000
34.0000000 0.0000000
0.0000000 1.0000000
34.0000000 1.0000000
0.0000000 2.0000000
34.0000000 2.0000000
0.0000000 3.0000000
34.0000000 3.0000000
0.0000000 4.0000000
34.0000000 4.0000000
0.0000000 5.0000000
34.0000000 5.0000000
0.0000000 6.0000000
34.0000000 6.0000000
0.0000000...

result:

ok correct

Test #32:

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

input:

34 99
104.6756896330

output:

4
0.0000000 0.0000000
0.0000000 0.0000000
34.0000000 99.0000000
34.0000000 99.0000000

result:

ok correct

Test #33:

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

input:

3 3
5.9999

output:

4
0.0000000 0.0000000
1.4999500 0.0000000
1.5000500 3.0000000
3.0000000 3.0000000

result:

ok correct

Test #34:

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

input:

3 3
6.0

output:

4
0.0000000 0.0000000
1.5000000 0.0000000
1.5000000 3.0000000
3.0000000 3.0000000

result:

ok correct

Test #35:

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

input:

3 3
6.0001

output:

4
0.0000000 0.0000000
1.5000500 0.0000000
1.4999500 3.0000000
3.0000000 3.0000000

result:

ok correct

Test #36:

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

input:

4 4
13.999998

output:

6
0.0000000 0.0000000
4.0000000 0.0000000
0.0000000 1.0000000
1.2704330 1.0000000
2.7295670 4.0000000
4.0000000 4.0000000

result:

ok correct

Test #37:

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

input:

4 4
14.0

output:

6
0.0000000 0.0000000
4.0000000 0.0000000
0.0000000 1.0000000
1.2704348 1.0000000
2.7295652 4.0000000
4.0000000 4.0000000

result:

ok correct

Test #38:

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

input:

4 4
14.000002

output:

6
0.0000000 0.0000000
4.0000000 0.0000000
0.0000000 1.0000000
1.2704365 1.0000000
2.7295635 4.0000000
4.0000000 4.0000000

result:

ok correct

Test #39:

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

input:

4 4
15.123104

output:

6
0.0000000 0.0000000
4.0000000 0.0000000
0.0000000 1.0000000
1.9999992 1.0000000
2.0000008 4.0000000
4.0000000 4.0000000

result:

ok correct

Test #40:

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

input:

4 4
15.123106

output:

6
0.0000000 0.0000000
4.0000000 0.0000000
0.0000000 1.0000000
2.0000002 1.0000000
1.9999998 4.0000000
4.0000000 4.0000000

result:

ok correct

Test #41:

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

input:

4 4
15.123108

output:

6
0.0000000 0.0000000
4.0000000 0.0000000
0.0000000 1.0000000
2.0000012 1.0000000
1.9999988 4.0000000
4.0000000 4.0000000

result:

ok correct

Test #42:

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

input:

4 4
14.593385

output:

6
0.0000000 0.0000000
4.0000000 0.0000000
0.0000000 1.0000000
1.7067417 1.0000000
2.2932583 4.0000000
4.0000000 4.0000000

result:

ok correct

Test #43:

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

input:

4 4
14.593387

output:

6
0.0000000 0.0000000
4.0000000 0.0000000
0.0000000 1.0000000
1.7067429 1.0000000
2.2932571 4.0000000
4.0000000 4.0000000

result:

ok correct

Test #44:

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

input:

4 4
14.593389

output:

6
0.0000000 0.0000000
4.0000000 0.0000000
0.0000000 1.0000000
1.7067442 1.0000000
2.2932558 4.0000000
4.0000000 4.0000000

result:

ok correct

Test #45:

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

input:

2 2
4.0

output:

4
0.0000000 0.0000000
1.0000000 0.0000000
1.0000000 2.0000000
2.0000000 2.0000000

result:

ok correct

Test #46:

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

input:

3 3
5.0

output:

4
0.0000000 0.0000000
0.8750000 0.0000000
2.1250000 3.0000000
3.0000000 3.0000000

result:

ok correct

Test #47:

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

input:

4 4
15.123

output:

6
0.0000000 0.0000000
4.0000000 0.0000000
0.0000000 1.0000000
1.9999472 1.0000000
2.0000528 4.0000000
4.0000000 4.0000000

result:

ok correct

Test #48:

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

input:

4 4
14.1

output:

6
0.0000000 0.0000000
4.0000000 0.0000000
0.0000000 1.0000000
1.3560748 1.0000000
2.6439252 4.0000000
4.0000000 4.0000000

result:

ok correct

Test #49:

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

input:

3 3
9.0

output:

4
0.0000000 0.0000000
2.6250000 0.0000000
0.3750000 3.0000000
3.0000000 3.0000000

result:

ok correct

Test #50:

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

input:

4 4
16.0

output:

6
0.0000000 0.0000000
4.0000000 0.0000000
0.0000000 1.0000000
2.3888622 1.0000000
1.6111378 4.0000000
4.0000000 4.0000000

result:

ok correct