QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#122528 | #2290. Kinking Cables | batrr# | AC ✓ | 2ms | 3808kb | C++17 | 1.8kb | 2023-07-10 17:58:49 | 2023-07-10 17:58:51 |
Judging History
answer
#include <bits/stdc++.h>
#define f first
#define s second
#define pb push_back
#define mp make_pair
using namespace std;
typedef long long ll;
using ld = long double;
typedef pair<int, int> pii;
typedef pair<long long, long long> pll;
const int N = 305, K = 30, inf = 1e9, mod = 998244353;
const ll INF = 1e18;
#define X first
#define Y second
ld dist(ld x, ld y, ld x2, ld y2)
{
return sqrt(abs(x-x2)*abs(x-x2)+abs(y-y2)*abs(y-y2));
}
void solve() {
int x = 0, y = 0;
vector<pair<ld,ld>> A;
int n, m;
cin >> n >> m;
ld L;
cin >> L;
A.push_back({0,0});
while (true)
{
int x2 = x, y2 = y;
if (x%2==0 and y==0) y2 = m;
if (x%2==0 and y==m) x2++;
if (x%2==1 and y==0) x2++;
if (x%2==1 and y==m) y2 = 0;
ld D = dist(x,y,x2,y2)+dist(x2,y2,n,m);
if (L>D)
{
L -= dist(x,y,x2,y2);
x = x2, y = y2;
A.push_back({x,y});
continue;
}
ld l = 0, r = 1;
for (int w=0;w<60;w++)
{
ld M = (l+r)/2;
ld x3 = x2*M+x*(1-M), y3 = y2*M+y*(1-M);
D = dist(x,y,x3,y3)+dist(x3,y3,n,m);
if (D<L) l = M;
else r = M;
}
ld x3 = x2*l+x*(1-l), y3 = y2*l+y*(1-l);
A.push_back({x3,y3});
A.push_back({n,m});
break;
}
cout.precision(20);
cout << A.size() << "\n";
for (int i=0;i<A.size();i++)
{
cout << A[i].X << " " << A[i].Y << "\n";
}
}
int main() {
#ifdef DEBUG
freopen("input.txt", "r", stdin);
#endif
ios_base::sync_with_stdio(false);
int t = 1;
// cin >> t;
for (int i = 1; i <= t; i++) {
// cout << "Case #" << i << endl;
solve();
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3592kb
input:
79 78 1980.7712136406
output:
49 0 0 0 78 1 78 1 0 2 0 2 78 3 78 3 0 4 0 4 78 5 78 5 0 6 0 6 78 7 78 7 0 8 0 8 78 9 78 9 0 10 0 10 78 11 78 11 0 12 0 12 78 13 78 13 0 14 0 14 78 15 78 15 0 16 0 16 78 17 78 17 0 18 0 18 78 19 78 19 0 20 0 20 78 21 78 21 0 22 0 22 78 23 78 23 5.6887253541016319872 79 78
result:
ok correct
Test #2:
score: 0
Accepted
time: 1ms
memory: 3600kb
input:
33 65 1947.7601065763
output:
61 0 0 0 65 1 65 1 0 2 0 2 65 3 65 3 0 4 0 4 65 5 65 5 0 6 0 6 65 7 65 7 0 8 0 8 65 9 65 9 0 10 0 10 65 11 65 11 0 12 0 12 65 13 65 13 0 14 0 14 65 15 65 15 0 16 0 16 65 17 65 17 0 18 0 18 65 19 65 19 0 20 0 20 65 21 65 21 0 22 0 22 65 23 65 23 0 24 0 24 65 25 65 25 0 26 0 26 65 27 65 27 0 28 0 28 6...
result:
ok correct
Test #3:
score: 0
Accepted
time: 1ms
memory: 3664kb
input:
51 51 555.0803652025
output:
21 0 0 0 51 1 51 1 0 2 0 2 51 3 51 3 0 4 0 4 51 5 51 5 0 6 0 6 51 7 51 7 0 8 0 8 51 9 51 9 17.588392284132756342 51 51
result:
ok correct
Test #4:
score: 0
Accepted
time: 1ms
memory: 3768kb
input:
49 2 67.3588717350
output:
21 0 0 0 2 1 2 1 0 2 0 2 2 3 2 3 0 4 0 4 2 5 2 5 0 6 0 6 2 7 2 7 0 8 0 8 2 9 2 9 1.6427238116127441635 49 2
result:
ok correct
Test #5:
score: 0
Accepted
time: 1ms
memory: 3728kb
input:
37 48 1713.3643608504
output:
70 0 0 0 48 1 48 1 0 2 0 2 48 3 48 3 0 4 0 4 48 5 48 5 0 6 0 6 48 7 48 7 0 8 0 8 48 9 48 9 0 10 0 10 48 11 48 11 0 12 0 12 48 13 48 13 0 14 0 14 48 15 48 15 0 16 0 16 48 17 48 17 0 18 0 18 48 19 48 19 0 20 0 20 48 21 48 21 0 22 0 22 48 23 48 23 0 24 0 24 48 25 48 25 0 26 0 26 48 27 48 27 0 28 0 28 4...
result:
ok correct
Test #6:
score: 0
Accepted
time: 1ms
memory: 3652kb
input:
51 79 820.1218304546
output:
21 0 0 0 79 1 79 1 0 2 0 2 79 3 79 3 0 4 0 4 79 5 79 5 0 6 0 6 79 7 79 7 0 8 0 8 79 9 79 9 37.748352401900414493 51 79
result:
ok correct
Test #7:
score: 0
Accepted
time: 1ms
memory: 3692kb
input:
6 8 37.5338494218
output:
9 0 0 0 8 1 8 1 0 2 0 2 8 3 8 3 3.1602695482743494229 6 8
result:
ok correct
Test #8:
score: 0
Accepted
time: 1ms
memory: 3692kb
input:
5 5 7.1908428511
output:
3 0 0 0 0.38985473293036429845 5 5
result:
ok correct
Test #9:
score: 0
Accepted
time: 1ms
memory: 3656kb
input:
5 4 8.3927665498
output:
3 0 0 0 3.3507961356132292437 5 4
result:
ok correct
Test #10:
score: 0
Accepted
time: 1ms
memory: 3788kb
input:
4 2 6.4617533647
output:
5 0 0 0 2 1 2 1 1.5690426145840771603 4 2
result:
ok correct
Test #11:
score: 0
Accepted
time: 1ms
memory: 3712kb
input:
91 87 4830.8473359767
output:
109 0 0 0 87 1 87 1 0 2 0 2 87 3 87 3 0 4 0 4 87 5 87 5 0 6 0 6 87 7 87 7 0 8 0 8 87 9 87 9 0 10 0 10 87 11 87 11 0 12 0 12 87 13 87 13 0 14 0 14 87 15 87 15 0 16 0 16 87 17 87 17 0 18 0 18 87 19 87 19 0 20 0 20 87 21 87 21 0 22 0 22 87 23 87 23 0 24 0 24 87 25 87 25 0 26 0 26 87 27 87 27 0 28 0 28 ...
result:
ok correct
Test #12:
score: 0
Accepted
time: 1ms
memory: 3600kb
input:
90 90 5088.9280941138
output:
113 0 0 0 90 1 90 1 0 2 0 2 90 3 90 3 0 4 0 4 90 5 90 5 0 6 0 6 90 7 90 7 0 8 0 8 90 9 90 9 0 10 0 10 90 11 90 11 0 12 0 12 90 13 90 13 0 14 0 14 90 15 90 15 0 16 0 16 90 17 90 17 0 18 0 18 90 19 90 19 0 20 0 20 90 21 90 21 0 22 0 22 90 23 90 23 0 24 0 24 90 25 90 25 0 26 0 26 90 27 90 27 0 28 0 28 ...
result:
ok correct
Test #13:
score: 0
Accepted
time: 1ms
memory: 3808kb
input:
90 92 7004.0153432299
output:
153 0 0 0 92 1 92 1 0 2 0 2 92 3 92 3 0 4 0 4 92 5 92 5 0 6 0 6 92 7 92 7 0 8 0 8 92 9 92 9 0 10 0 10 92 11 92 11 0 12 0 12 92 13 92 13 0 14 0 14 92 15 92 15 0 16 0 16 92 17 92 17 0 18 0 18 92 19 92 19 0 20 0 20 92 21 92 21 0 22 0 22 92 23 92 23 0 24 0 24 92 25 92 25 0 26 0 26 92 27 92 27 0 28 0 28 ...
result:
ok correct
Test #14:
score: 0
Accepted
time: 1ms
memory: 3768kb
input:
91 83 1879.3819547895
output:
45 0 0 0 83 1 83 1 0 2 0 2 83 3 83 3 0 4 0 4 83 5 83 5 0 6 0 6 83 7 83 7 0 8 0 8 83 9 83 9 0 10 0 10 83 11 83 11 0 12 0 12 83 13 83 13 0 14 0 14 83 15 83 15 0 16 0 16 83 17 83 17 0 18 0 18 83 19 83 19 0 20 0 20 83 21 83 21 46.542845558498796461 91 83
result:
ok correct
Test #15:
score: 0
Accepted
time: 1ms
memory: 3732kb
input:
3 81 199.2077743610
output:
5 0 0 0 81 1 81 1 22.413176534009585391 3 81
result:
ok correct
Test #16:
score: 0
Accepted
time: 1ms
memory: 3792kb
input:
4 89 288.5915130114
output:
9 0 0 0 89 1 89 1 0 2 0 2 89 3 89 3 79.73113748618185543 4 89
result:
ok correct
Test #17:
score: 0
Accepted
time: 0ms
memory: 3772kb
input:
95 3 175.9210001082
output:
55 0 0 0 3 1 3 1 0 2 0 2 3 3 3 3 0 4 0 4 3 5 3 5 0 6 0 6 3 7 3 7 0 8 0 8 3 9 3 9 0 10 0 10 3 11 3 11 0 12 0 12 3 13 3 13 0 14 0 14 3 15 3 15 0 16 0 16 3 17 3 17 0 18 0 18 3 19 3 19 0 20 0 20 3 21 3 21 0 22 0 22 3 23 3 23 0 24 0 24 3 25 3 25 0 26 0 26 2.9209548318481289098 95 3
result:
ok correct
Test #18:
score: 0
Accepted
time: 1ms
memory: 3796kb
input:
84 4 310.3037172015
output:
115 0 0 0 4 1 4 1 0 2 0 2 4 3 4 3 0 4 0 4 4 5 4 5 0 6 0 6 4 7 4 7 0 8 0 8 4 9 4 9 0 10 0 10 4 11 4 11 0 12 0 12 4 13 4 13 0 14 0 14 4 15 4 15 0 16 0 16 4 17 4 17 0 18 0 18 4 19 4 19 0 20 0 20 4 21 4 21 0 22 0 22 4 23 4 23 0 24 0 24 4 25 4 25 0 26 0 26 4 27 4 27 0 28 0 28 4 29 4 29 0 30 0 30 4 31 4 3...
result:
ok correct
Test #19:
score: 0
Accepted
time: 1ms
memory: 3604kb
input:
2 2 2.8284271248
output:
3 0 0 0 1.8371849701270814847e-10 2 2
result:
ok correct
Test #20:
score: 0
Accepted
time: 1ms
memory: 3704kb
input:
100 100 10000.0000000000
output:
199 0 0 0 100 1 100 1 0 2 0 2 100 3 100 3 0 4 0 4 100 5 100 5 0 6 0 6 100 7 100 7 0 8 0 8 100 9 100 9 0 10 0 10 100 11 100 11 0 12 0 12 100 13 100 13 0 14 0 14 100 15 100 15 0 16 0 16 100 17 100 17 0 18 0 18 100 19 100 19 0 20 0 20 100 21 100 21 0 22 0 22 100 23 100 23 0 24 0 24 100 25 100 25 0 26 0...
result:
ok correct
Test #21:
score: 0
Accepted
time: 0ms
memory: 3620kb
input:
100 100 9999.2500000000
output:
199 0 0 0 100 1 100 1 0 2 0 2 100 3 100 3 0 4 0 4 100 5 100 5 0 6 0 6 100 7 100 7 0 8 0 8 100 9 100 9 0 10 0 10 100 11 100 11 0 12 0 12 100 13 100 13 0 14 0 14 100 15 100 15 0 16 0 16 100 17 100 17 0 18 0 18 100 19 100 19 0 20 0 20 100 21 100 21 0 22 0 22 100 23 100 23 0 24 0 24 100 25 100 25 0 26 0...
result:
ok correct
Test #22:
score: 0
Accepted
time: 1ms
memory: 3596kb
input:
100 100 2723.8981892905
output:
53 0 0 0 100 1 100 1 0 2 0 2 100 3 100 3 0 4 0 4 100 5 100 5 0 6 0 6 100 7 100 7 0 8 0 8 100 9 100 9 0 10 0 10 100 11 100 11 0 12 0 12 100 13 100 13 0 14 0 14 100 15 100 15 0 16 0 16 100 17 100 17 0 18 0 18 100 19 100 19 0 20 0 20 100 21 100 21 0 22 0 22 100 23 100 23 0 24 0 24 100 25 100 25 14.6913...
result:
ok correct
Test #23:
score: 0
Accepted
time: 1ms
memory: 3720kb
input:
100 100 8994.4904261819
output:
179 0 0 0 100 1 100 1 0 2 0 2 100 3 100 3 0 4 0 4 100 5 100 5 0 6 0 6 100 7 100 7 0 8 0 8 100 9 100 9 0 10 0 10 100 11 100 11 0 12 0 12 100 13 100 13 0 14 0 14 100 15 100 15 0 16 0 16 100 17 100 17 0 18 0 18 100 19 100 19 0 20 0 20 100 21 100 21 0 22 0 22 100 23 100 23 0 24 0 24 100 25 100 25 0 26 0...
result:
ok correct
Test #24:
score: 0
Accepted
time: 1ms
memory: 3712kb
input:
100 100 881.4998747190
output:
17 0 0 0 100 1 100 1 0 2 0 2 100 3 100 3 0 4 0 4 100 5 100 5 0 6 0 6 100 7 100 7 37.532315389757344923 100 100
result:
ok correct
Test #25:
score: 0
Accepted
time: 0ms
memory: 3676kb
input:
88 94 8266.2500000000
output:
177 0 0 0 94 1 94 1 0 2 0 2 94 3 94 3 0 4 0 4 94 5 94 5 0 6 0 6 94 7 94 7 0 8 0 8 94 9 94 9 0 10 0 10 94 11 94 11 0 12 0 12 94 13 94 13 0 14 0 14 94 15 94 15 0 16 0 16 94 17 94 17 0 18 0 18 94 19 94 19 0 20 0 20 94 21 94 21 0 22 0 22 94 23 94 23 0 24 0 24 94 25 94 25 0 26 0 26 94 27 94 27 0 28 0 28 ...
result:
ok correct
Test #26:
score: 0
Accepted
time: 1ms
memory: 3680kb
input:
75 37 2772.0000000000
output:
145 0 0 0 37 1 37 1 0 2 0 2 37 3 37 3 0 4 0 4 37 5 37 5 0 6 0 6 37 7 37 7 0 8 0 8 37 9 37 9 0 10 0 10 37 11 37 11 0 12 0 12 37 13 37 13 0 14 0 14 37 15 37 15 0 16 0 16 37 17 37 17 0 18 0 18 37 19 37 19 0 20 0 20 37 21 37 21 0 22 0 22 37 23 37 23 0 24 0 24 37 25 37 25 0 26 0 26 37 27 37 27 0 28 0 28 ...
result:
ok correct
Test #27:
score: 0
Accepted
time: 1ms
memory: 3788kb
input:
48 39 62.0000000000
output:
3 0 0 0 0.41304347826086954942 48 39
result:
ok correct
Test #28:
score: 0
Accepted
time: 1ms
memory: 3788kb
input:
98 94 135.9000000000
output:
3 0 0 0 0.34379474940334120783 98 94
result:
ok correct
Test #29:
score: 0
Accepted
time: 1ms
memory: 3788kb
input:
90 81 7290.0000000000
output:
177 0 0 0 81 1 81 1 0 2 0 2 81 3 81 3 0 4 0 4 81 5 81 5 0 6 0 6 81 7 81 7 0 8 0 8 81 9 81 9 0 10 0 10 81 11 81 11 0 12 0 12 81 13 81 13 0 14 0 14 81 15 81 15 0 16 0 16 81 17 81 17 0 18 0 18 81 19 81 19 0 20 0 20 81 21 81 21 0 22 0 22 81 23 81 23 0 24 0 24 81 25 81 25 0 26 0 26 81 27 81 27 0 28 0 28 ...
result:
ok correct
Test #30:
score: 0
Accepted
time: 1ms
memory: 3736kb
input:
90 81 121.0826164250
output:
3 0 0 0 4.0376577784342893018e-09 90 81
result:
ok correct
Test #31:
score: 0
Accepted
time: 1ms
memory: 3612kb
input:
34 99 3366.0000000000
output:
69 0 0 0 99 1 99 1 0 2 0 2 99 3 99 3 0 4 0 4 99 5 99 5 0 6 0 6 99 7 99 7 0 8 0 8 99 9 99 9 0 10 0 10 99 11 99 11 0 12 0 12 99 13 99 13 0 14 0 14 99 15 99 15 0 16 0 16 99 17 99 17 0 18 0 18 99 19 99 19 0 20 0 20 99 21 99 21 0 22 0 22 99 23 99 23 0 24 0 24 99 25 99 25 0 26 0 26 99 27 99 27 0 28 0 28 9...
result:
ok correct
Test #32:
score: 0
Accepted
time: 1ms
memory: 3688kb
input:
34 99 104.6756896330
output:
3 0 0 0 1.2698339949858417075e-08 34 99
result:
ok correct
Test #33:
score: 0
Accepted
time: 1ms
memory: 3660kb
input:
3 3 5.9999
output:
3 0 0 0 2.9998999983332777742 3 3
result:
ok correct
Test #34:
score: 0
Accepted
time: 1ms
memory: 3692kb
input:
3 3 6.0
output:
3 0 0 0 2.9999999999999999974 3 3
result:
ok correct
Test #35:
score: 0
Accepted
time: 1ms
memory: 3764kb
input:
3 3 6.0001
output:
5 0 0 0 3 1 3 1 2.9999000024998750081 3 3
result:
ok correct
Test #36:
score: 0
Accepted
time: 1ms
memory: 3704kb
input:
4 4 13.999998
output:
5 0 0 0 4 1 4 1 1.1111111358035052898e-06 4 4
result:
ok correct
Test #37:
score: 0
Accepted
time: 1ms
memory: 3788kb
input:
4 4 14.0
output:
5 0 0 0 4 1 4 1 3.4694469519536141888e-18 4 4
result:
ok correct
Test #38:
score: 0
Accepted
time: 1ms
memory: 3688kb
input:
4 4 14.000002
output:
6 0 0 0 4 1 4 1 0 1.0000049999960000041 0 4 4
result:
ok correct
Test #39:
score: 0
Accepted
time: 1ms
memory: 3696kb
input:
4 4 15.123104
output:
7 0 0 0 4 1 4 1 0 2 0 2 2.7807730160412570848 4 4
result:
ok correct
Test #40:
score: 0
Accepted
time: 0ms
memory: 3600kb
input:
4 4 15.123106
output:
7 0 0 0 4 1 4 1 0 2 0 2 2.7807771872093996444 4 4
result:
ok correct
Test #41:
score: 0
Accepted
time: 1ms
memory: 3776kb
input:
4 4 15.123108
output:
7 0 0 0 4 1 4 1 0 2 0 2 2.7807813583662479469 4 4
result:
ok correct
Test #42:
score: 0
Accepted
time: 1ms
memory: 3656kb
input:
4 4 14.593385
output:
7 0 0 0 4 1 4 1 0 2 0 2 0.92619948113366532341 4 4
result:
ok correct
Test #43:
score: 0
Accepted
time: 0ms
memory: 3608kb
input:
4 4 14.593387
output:
7 0 0 0 4 1 4 1 0 2 0 2 0.92621184131856612934 4 4
result:
ok correct
Test #44:
score: 0
Accepted
time: 1ms
memory: 3664kb
input:
4 4 14.593389
output:
7 0 0 0 4 1 4 1 0 2 0 2 0.92622420142688859437 4 4
result:
ok correct
Test #45:
score: 0
Accepted
time: 1ms
memory: 3736kb
input:
2 2 4.0
output:
3 0 0 0 1.9999999999999999983 2 2
result:
ok correct
Test #46:
score: 0
Accepted
time: 2ms
memory: 3764kb
input:
3 3 5.0
output:
3 0 0 0 1.7499999999999999991 3 3
result:
ok correct
Test #47:
score: 0
Accepted
time: 1ms
memory: 3656kb
input:
4 4 15.123
output:
7 0 0 0 4 1 4 1 0 2 0 2 2.7805560997328584126 4 4
result:
ok correct
Test #48:
score: 0
Accepted
time: 2ms
memory: 3720kb
input:
4 4 14.1
output:
6 0 0 0 4 1 4 1 0 1.2404761904761904762 0 4 4
result:
ok correct
Test #49:
score: 0
Accepted
time: 1ms
memory: 3704kb
input:
3 3 9.0
output:
5 0 0 0 3 1 3 1 0.90000000000000000052 3 3
result:
ok correct
Test #50:
score: 0
Accepted
time: 1ms
memory: 3656kb
input:
4 4 16.0
output:
7 0 0 0 4 1 4 1 0 2 0 2 3.9999999999999999965 4 4
result:
ok correct