QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#372249#2290. Kinking Cableskevinyang#AC ✓1ms4028kbC++172.9kb2024-03-31 07:11:452024-03-31 07:11:46

Judging History

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

  • [2024-03-31 07:11:46]
  • 评测
  • 测评结果:AC
  • 用时:1ms
  • 内存:4028kb
  • [2024-03-31 07:11:45]
  • 提交

answer

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

template <class T> int sgn(T x) { return (x > 0) - (x < 0); }
template<class T>
struct Point {
	typedef Point P;
	T x, y;
	explicit Point(T x=0, T y=0) : x(x), y(y) {}
	bool operator<(P p) const { return tie(x,y) < tie(p.x,p.y); }
	bool operator==(P p) const { return tie(x,y)==tie(p.x,p.y); }
	bool operator!=(P p) const { return tie(x,y)!=tie(p.x,p.y); }
	P operator+(P p) const { return P(x+p.x, y+p.y); }
	P operator-(P p) const { return P(x-p.x, y-p.y); }
	P operator*(T d) const { return P(x*d, y*d); }
	P operator/(T d) const { return P(x/d, y/d); }
	T dot(P p) const { return x*p.x + y*p.y; }
	T cross(P p) const { return x*p.y - y*p.x; }
	T cross(P a, P b) const { return (a-*this).cross(b-*this); }
	T dist2() const { return x*x + y*y; }
	double dist() const { return sqrt((double)dist2()); }
	// angle to x-axis in interval [-pi, pi]
	double angle() const { return atan2(y, x); }
	P unit() const { return *this/dist(); } // makes dist()=1
	P perp() const { return P(-y, x); } // rotates +90 degrees
	P normal() const { return perp().unit(); }
	// returns point rotated 'a' radians ccw around the origin
	P rotate(double a) const {
		return P(x*cos(a)-y*sin(a),x*sin(a)+y*cos(a)); }
	friend ostream& operator<<(ostream& os, P p) {
		return os << p.x << " " << p.y ; }
};

typedef Point<double> P;

signed main(){
	cin.tie(nullptr)->sync_with_stdio(false);
	int n,m;
	cin >> m >> n;
	double l;
	cin >> l;
	vector<P>ans;
	ans.push_back(P{0,0});
	P cur{0,0};
	double d = 0;
	int i = 1;
	P end{(double)m,(double)n};
	int cury = 0;
	while(true){
		if(i%2==1){
			P p{(double)m,cur.y};
			if(d+(p-cur).dist() + (p-end).dist() < l){
				if(ans.back()!=p)ans.push_back(p);
				d+=(p-cur).dist();
				cur = p;
			}
			else{
				double low = 0; double high = m;
				for(int iters = 0; iters < 100; iters++){
					double mid = (low+high)/2;
					P p2{mid,cur.y};

					if(d+(p2-cur).dist() + (p2-end).dist() < l){
						low = mid;
					}
					else{
						high = mid;
					}
				}
				P p2{low,cur.y};
				if(ans.back()!=p2)ans.push_back(p2);
				break;
			}
		}
		else{
			P p{0,(double)(i/2)};
			if(d+(p-cur).dist() + (p-end).dist() < l){
				if(ans.back()!=p)ans.push_back(p);
				d+=(p-cur).dist();
				cur = p;
			}
			else{
				double low = 0; double high = m;
				for(int iters = 0; iters < 100; iters++){
					double mid = (low+high)/2;
					P p2{mid,(double)(i/2)};
					if(d+(p2-cur).dist() + (p2-end).dist() > l){
						low = mid;
					}
					else{
						high = mid;
					}
				}
				P p2{low,(double)(i/2)};
				if(ans.back()!=p2)ans.push_back(p2);
				//cout << "gay\n";
				break;
			}
		}
		i++;
	}
	ans.push_back(end);
	cout << ans.size() << '\n';
	cout << fixed << setprecision(10);
	for(auto nxt: ans){
		cout << nxt << '\n';
	}
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

79 78
1980.7712136406

output:

26
0.0000000000 0.0000000000
79.0000000000 0.0000000000
0.0000000000 1.0000000000
79.0000000000 1.0000000000
0.0000000000 2.0000000000
79.0000000000 2.0000000000
0.0000000000 3.0000000000
79.0000000000 3.0000000000
0.0000000000 4.0000000000
79.0000000000 4.0000000000
0.0000000000 5.0000000000
79.000...

result:

ok correct

Test #2:

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

input:

33 65
1947.7601065763

output:

60
0.0000000000 0.0000000000
33.0000000000 0.0000000000
0.0000000000 1.0000000000
33.0000000000 1.0000000000
0.0000000000 2.0000000000
33.0000000000 2.0000000000
0.0000000000 3.0000000000
33.0000000000 3.0000000000
0.0000000000 4.0000000000
33.0000000000 4.0000000000
0.0000000000 5.0000000000
33.000...

result:

ok correct

Test #3:

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

input:

51 51
555.0803652025

output:

12
0.0000000000 0.0000000000
51.0000000000 0.0000000000
0.0000000000 1.0000000000
51.0000000000 1.0000000000
0.0000000000 2.0000000000
51.0000000000 2.0000000000
0.0000000000 3.0000000000
51.0000000000 3.0000000000
0.0000000000 4.0000000000
51.0000000000 4.0000000000
14.0038406511 5.0000000000
51.00...

result:

ok correct

Test #4:

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

input:

49 2
67.3588717350

output:

4
0.0000000000 0.0000000000
49.0000000000 0.0000000000
39.8751962845 1.0000000000
49.0000000000 2.0000000000

result:

ok correct

Test #5:

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

input:

37 48
1713.3643608504

output:

48
0.0000000000 0.0000000000
37.0000000000 0.0000000000
0.0000000000 1.0000000000
37.0000000000 1.0000000000
0.0000000000 2.0000000000
37.0000000000 2.0000000000
0.0000000000 3.0000000000
37.0000000000 3.0000000000
0.0000000000 4.0000000000
37.0000000000 4.0000000000
0.0000000000 5.0000000000
37.000...

result:

ok correct

Test #6:

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

input:

51 79
820.1218304546

output:

17
0.0000000000 0.0000000000
51.0000000000 0.0000000000
0.0000000000 1.0000000000
51.0000000000 1.0000000000
0.0000000000 2.0000000000
51.0000000000 2.0000000000
0.0000000000 3.0000000000
51.0000000000 3.0000000000
0.0000000000 4.0000000000
51.0000000000 4.0000000000
0.0000000000 5.0000000000
51.000...

result:

ok correct

Test #7:

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

input:

6 8
37.5338494218

output:

8
0.0000000000 0.0000000000
6.0000000000 0.0000000000
0.0000000000 1.0000000000
6.0000000000 1.0000000000
0.0000000000 2.0000000000
6.0000000000 2.0000000000
4.2040697452 3.0000000000
6.0000000000 8.0000000000

result:

ok correct

Test #8:

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

input:

5 5
7.1908428511

output:

3
0.0000000000 0.0000000000
0.3898547329 0.0000000000
5.0000000000 5.0000000000

result:

ok correct

Test #9:

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

input:

5 4
8.3927665498

output:

3
0.0000000000 0.0000000000
4.3384255780 0.0000000000
5.0000000000 4.0000000000

result:

ok correct

Test #10:

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

input:

4 2
6.4617533647

output:

4
0.0000000000 0.0000000000
4.0000000000 0.0000000000
3.2823249989 1.0000000000
4.0000000000 2.0000000000

result:

ok correct

Test #11:

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

input:

91 87
4830.8473359767

output:

54
0.0000000000 0.0000000000
91.0000000000 0.0000000000
0.0000000000 1.0000000000
91.0000000000 1.0000000000
0.0000000000 2.0000000000
91.0000000000 2.0000000000
0.0000000000 3.0000000000
91.0000000000 3.0000000000
0.0000000000 4.0000000000
91.0000000000 4.0000000000
0.0000000000 5.0000000000
91.000...

result:

ok correct

Test #12:

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

input:

90 90
5088.9280941138

output:

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

result:

ok correct

Test #13:

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

input:

90 92
7004.0153432299

output:

80
0.0000000000 0.0000000000
90.0000000000 0.0000000000
0.0000000000 1.0000000000
90.0000000000 1.0000000000
0.0000000000 2.0000000000
90.0000000000 2.0000000000
0.0000000000 3.0000000000
90.0000000000 3.0000000000
0.0000000000 4.0000000000
90.0000000000 4.0000000000
0.0000000000 5.0000000000
90.000...

result:

ok correct

Test #14:

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

input:

91 83
1879.3819547895

output:

22
0.0000000000 0.0000000000
91.0000000000 0.0000000000
0.0000000000 1.0000000000
91.0000000000 1.0000000000
0.0000000000 2.0000000000
91.0000000000 2.0000000000
0.0000000000 3.0000000000
91.0000000000 3.0000000000
0.0000000000 4.0000000000
91.0000000000 4.0000000000
0.0000000000 5.0000000000
91.000...

result:

ok correct

Test #15:

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

input:

3 81
199.2077743610

output:

48
0.0000000000 0.0000000000
3.0000000000 0.0000000000
0.0000000000 1.0000000000
3.0000000000 1.0000000000
0.0000000000 2.0000000000
3.0000000000 2.0000000000
0.0000000000 3.0000000000
3.0000000000 3.0000000000
0.0000000000 4.0000000000
3.0000000000 4.0000000000
0.0000000000 5.0000000000
3.000000000...

result:

ok correct

Test #16:

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

input:

4 89
288.5915130114

output:

59
0.0000000000 0.0000000000
4.0000000000 0.0000000000
0.0000000000 1.0000000000
4.0000000000 1.0000000000
0.0000000000 2.0000000000
4.0000000000 2.0000000000
0.0000000000 3.0000000000
4.0000000000 3.0000000000
0.0000000000 4.0000000000
4.0000000000 4.0000000000
0.0000000000 5.0000000000
4.000000000...

result:

ok correct

Test #17:

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

input:

95 3
175.9210001082

output:

4
0.0000000000 0.0000000000
95.0000000000 0.0000000000
54.5704018294 1.0000000000
95.0000000000 3.0000000000

result:

ok correct

Test #18:

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

input:

84 4
310.3037172015

output:

6
0.0000000000 0.0000000000
84.0000000000 0.0000000000
0.0000000000 1.0000000000
84.0000000000 1.0000000000
54.8940209932 2.0000000000
84.0000000000 4.0000000000

result:

ok correct

Test #19:

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

input:

2 2
2.8284271248

output:

3
0.0000000000 0.0000000000
0.0000000002 0.0000000000
2.0000000000 2.0000000000

result:

ok correct

Test #20:

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

input:

100 100
10000.0000000000

output:

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

result:

ok correct

Test #21:

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

input:

100 100
9999.2500000000

output:

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

result:

ok correct

Test #22:

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

input:

100 100
2723.8981892905

output:

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

result:

ok correct

Test #23:

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

input:

100 100
8994.4904261819

output:

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

result:

ok correct

Test #24:

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

input:

100 100
881.4998747190

output:

10
0.0000000000 0.0000000000
100.0000000000 0.0000000000
0.0000000000 1.0000000000
100.0000000000 1.0000000000
0.0000000000 2.0000000000
100.0000000000 2.0000000000
0.0000000000 3.0000000000
100.0000000000 3.0000000000
34.6530040334 4.0000000000
100.0000000000 100.0000000000

result:

ok correct

Test #25:

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

input:

88 94
8266.2500000000

output:

96
0.0000000000 0.0000000000
88.0000000000 0.0000000000
0.0000000000 1.0000000000
88.0000000000 1.0000000000
0.0000000000 2.0000000000
88.0000000000 2.0000000000
0.0000000000 3.0000000000
88.0000000000 3.0000000000
0.0000000000 4.0000000000
88.0000000000 4.0000000000
0.0000000000 5.0000000000
88.000...

result:

ok correct

Test #26:

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

input:

75 37
2772.0000000000

output:

38
0.0000000000 0.0000000000
75.0000000000 0.0000000000
0.0000000000 1.0000000000
75.0000000000 1.0000000000
0.0000000000 2.0000000000
75.0000000000 2.0000000000
0.0000000000 3.0000000000
75.0000000000 3.0000000000
0.0000000000 4.0000000000
75.0000000000 4.0000000000
0.0000000000 5.0000000000
75.000...

result:

ok correct

Test #27:

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

input:

48 39
62.0000000000

output:

3
0.0000000000 0.0000000000
0.6785714286 0.0000000000
48.0000000000 39.0000000000

result:

ok correct

Test #28:

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

input:

98 94
135.9000000000

output:

3
0.0000000000 0.0000000000
0.3800791557 0.0000000000
98.0000000000 94.0000000000

result:

ok correct

Test #29:

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

input:

90 81
7290.0000000000

output:

82
0.0000000000 0.0000000000
90.0000000000 0.0000000000
0.0000000000 1.0000000000
90.0000000000 1.0000000000
0.0000000000 2.0000000000
90.0000000000 2.0000000000
0.0000000000 3.0000000000
90.0000000000 3.0000000000
0.0000000000 4.0000000000
90.0000000000 4.0000000000
0.0000000000 5.0000000000
90.000...

result:

ok correct

Test #30:

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

input:

90 81
121.0826164250

output:

3
0.0000000000 0.0000000000
0.0000000052 0.0000000000
90.0000000000 81.0000000000

result:

ok correct

Test #31:

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

input:

34 99
3366.0000000000

output:

100
0.0000000000 0.0000000000
34.0000000000 0.0000000000
0.0000000000 1.0000000000
34.0000000000 1.0000000000
0.0000000000 2.0000000000
34.0000000000 2.0000000000
0.0000000000 3.0000000000
34.0000000000 3.0000000000
0.0000000000 4.0000000000
34.0000000000 4.0000000000
0.0000000000 5.0000000000
34.00...

result:

ok correct

Test #32:

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

input:

34 99
104.6756896330

output:

3
0.0000000000 0.0000000000
0.0000000010 0.0000000000
34.0000000000 99.0000000000

result:

ok correct

Test #33:

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

input:

3 3
5.9999

output:

3
0.0000000000 0.0000000000
2.9998999983 0.0000000000
3.0000000000 3.0000000000

result:

ok correct

Test #34:

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

input:

3 3
6.0

output:

3
0.0000000000 0.0000000000
3.0000000000 0.0000000000
3.0000000000 3.0000000000

result:

ok correct

Test #35:

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

input:

3 3
6.0001

output:

4
0.0000000000 0.0000000000
3.0000000000 0.0000000000
2.9884528503 1.0000000000
3.0000000000 3.0000000000

result:

ok correct

Test #36:

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

input:

4 4
13.999998

output:

5
0.0000000000 0.0000000000
4.0000000000 0.0000000000
0.0000000000 1.0000000000
2.5408659842 1.0000000000
4.0000000000 4.0000000000

result:

ok correct

Test #37:

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

input:

4 4
14.0

output:

5
0.0000000000 0.0000000000
4.0000000000 0.0000000000
0.0000000000 1.0000000000
2.5408695390 1.0000000000
4.0000000000 4.0000000000

result:

ok correct

Test #38:

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

input:

4 4
14.000002

output:

5
0.0000000000 0.0000000000
4.0000000000 0.0000000000
0.0000000000 1.0000000000
2.5408730939 1.0000000000
4.0000000000 4.0000000000

result:

ok correct

Test #39:

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

input:

4 4
15.123104

output:

5
0.0000000000 0.0000000000
4.0000000000 0.0000000000
0.0000000000 1.0000000000
3.9999983744 1.0000000000
4.0000000000 4.0000000000

result:

ok correct

Test #40:

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

input:

4 4
15.123106

output:

6
0.0000000000 0.0000000000
4.0000000000 0.0000000000
0.0000000000 1.0000000000
4.0000000000 1.0000000000
3.9992934758 2.0000000000
4.0000000000 4.0000000000

result:

ok correct

Test #41:

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

input:

4 4
15.123108

output:

6
0.0000000000 0.0000000000
4.0000000000 0.0000000000
0.0000000000 1.0000000000
4.0000000000 1.0000000000
3.9982207178 2.0000000000
4.0000000000 4.0000000000

result:

ok correct

Test #42:

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

input:

4 4
14.593385

output:

5
0.0000000000 0.0000000000
4.0000000000 0.0000000000
0.0000000000 1.0000000000
3.4134833812 1.0000000000
4.0000000000 4.0000000000

result:

ok correct

Test #43:

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

input:

4 4
14.593387

output:

5
0.0000000000 0.0000000000
4.0000000000 0.0000000000
0.0000000000 1.0000000000
3.4134858560 1.0000000000
4.0000000000 4.0000000000

result:

ok correct

Test #44:

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

input:

4 4
14.593389

output:

5
0.0000000000 0.0000000000
4.0000000000 0.0000000000
0.0000000000 1.0000000000
3.4134883309 1.0000000000
4.0000000000 4.0000000000

result:

ok correct

Test #45:

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

input:

2 2
4.0

output:

3
0.0000000000 0.0000000000
2.0000000000 0.0000000000
2.0000000000 2.0000000000

result:

ok correct

Test #46:

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

input:

3 3
5.0

output:

3
0.0000000000 0.0000000000
1.7500000000 0.0000000000
3.0000000000 3.0000000000

result:

ok correct

Test #47:

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

input:

4 4
15.123

output:

5
0.0000000000 0.0000000000
4.0000000000 0.0000000000
0.0000000000 1.0000000000
3.9998943725 1.0000000000
4.0000000000 4.0000000000

result:

ok correct

Test #48:

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

input:

4 4
14.1

output:

5
0.0000000000 0.0000000000
4.0000000000 0.0000000000
0.0000000000 1.0000000000
2.7121495467 1.0000000000
4.0000000000 4.0000000000

result:

ok correct

Test #49:

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

input:

3 3
9.0

output:

4
0.0000000000 0.0000000000
3.0000000000 0.0000000000
0.4382623085 1.0000000000
3.0000000000 3.0000000000

result:

ok correct

Test #50:

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

input:

4 4
16.0

output:

6
0.0000000000 0.0000000000
4.0000000000 0.0000000000
0.0000000000 1.0000000000
4.0000000000 1.0000000000
2.8137137745 2.0000000000
4.0000000000 4.0000000000

result:

ok correct