QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#134387 | #2290. Kinking Cables | PetroTarnavskyi# | AC ✓ | 3ms | 3836kb | C++17 | 1.8kb | 2023-08-03 18:45:40 | 2023-08-03 18:45:43 |
Judging History
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