QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#372249 | #2290. Kinking Cables | kevinyang# | AC ✓ | 1ms | 4028kb | C++17 | 2.9kb | 2024-03-31 07:11:45 | 2024-03-31 07:11:46 |
Judging History
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