QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#134341 | #2290. Kinking Cables | mshcherba# | AC ✓ | 2ms | 3984kb | C++17 | 3.6kb | 2023-08-03 17:28:11 | 2023-08-03 17:28:14 |
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;
const db EPS = 1e-9;
struct Point {
db x, y;
Point() {}
Point(db _x, db _y): x(_x), y(_y) {}
Point operator+(const Point& p) const {
return {x + p.x, y + p.y};
}
Point operator-(const Point& p) const {
return {x - p.x, y - p.y};
}
db operator*(const Point& p) const {
return x * p.y - p.x * y;
}
db d2() const {
return x * x + y * y;
}
db len() const {
return sqrt(d2());
}
Point scale(db l) const {
l /= len();
return Point(x * l, y * l);
}
};
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout << fixed << setprecision(10);
int n, m;
db l;
cin >> n >> m >> l;
bool sw = n > m;
if (sw) {
swap(n, m);
}
db l0 = l;
Point p(0, 0), last(n, m);
vector<Point> ans = {{0, 0}};
vector<int> ys(m);
iota(ALL(ys), 0);
FOR(i, 0, n) {
for (int j : ys) {
if (l < -1) {
break;
}
Point cur(i, j);
if ((Point(n, m - 1) - p).len() + 1 < l + EPS && (Point(n, 0) - p).len() + m > l - EPS) {
cerr << "a" << endl;
double low = 0, high = m - 1;
FOR(it, 0, 74) {
double mid = (low + high) / 2;
if ((Point(n, mid) - p).len() + m - mid < l) {
high = mid;
}
else {
low = mid;
}
}
ans.emplace_back(n, low);
ans.emplace_back(last);
l = -47;
}
else if ((Point(n - 1, m) - p).len() + 1 < l + EPS && (Point(i, m) - p).len() + n - i > l - EPS) {
cerr << "b" << endl;
double low = i, high = n - 1;
FOR(it, 0, 74) {
double mid = (low + high) / 2;
if ((Point(mid, m) - p).len() + n - mid < l) {
high = mid;
}
else {
low = mid;
}
}
ans.emplace_back(low, m);
ans.emplace_back(last);
l = -47;
}
else if ((cur - p).len() + (last - cur).len() < l + EPS) {
l -= (cur - p).len();
p = cur;
ans.push_back(p);
}
else {
cerr << "c" << endl;
Point mid = p + last;
mid.x /= 2;
mid.y /= 2;
Point v(p.y - last.y, last.x - p.x);
db len = sqrt(max((db)0, l * l - (last - p).d2())) / 2;
ans.push_back(mid + v.scale(len));
if (ans.back().x < -EPS || ans.back().x > n + EPS || ans.back().y < -EPS || ans.back().y > m + EPS) {
cerr << ans.back().x << " " << ans.back().y << endl;
ans.pop_back();
ans.push_back(mid - v.scale(len));
}
ans.push_back(last);
l = -47;
}
}
reverse(ALL(ys));
}
vector<Point> newAns;
for (const Point & pi : ans) {
if (SZ(newAns) > 1 && abs((newAns.back() - newAns[SZ(newAns) - 2]) * (pi - newAns.back())) / (pi - newAns.back()).len() < EPS) {
newAns.pop_back();
}
newAns.push_back(pi);
}
ans = newAns;
cout << SZ(ans) << "\n";
for (Point& pi : ans) {
assert(pi.x > -EPS && pi.x < n + EPS && pi.y > -EPS && pi.y < m + EPS);
if (sw) {
swap(pi.x, pi.y);
}
cout << pi.x << " " << pi.y << "\n";
}
db ul = 0;
FOR(i, 0, SZ(ans) - 1) {
ul += (ans[i + 1] - ans[i]).len();
}
assert(abs(ul - l0) / l0 < 1e-6);
FOR(i, 0, SZ(ans)) {
FOR(j, 0, i) {
assert((ans[j] - ans[i]).len() > 1 - EPS);
}
}
assert(SZ(ans) <= 500);
cerr << ul << endl;
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3764kb
input:
79 78 1980.7712136406
output:
48 0.0000000000 0.0000000000 78.0000000000 0.0000000000 78.0000000000 1.0000000000 0.0000000000 1.0000000000 0.0000000000 2.0000000000 78.0000000000 2.0000000000 78.0000000000 3.0000000000 0.0000000000 3.0000000000 0.0000000000 4.0000000000 78.0000000000 4.0000000000 78.0000000000 5.0000000000 0.000...
result:
ok correct
Test #2:
score: 0
Accepted
time: 1ms
memory: 3984kb
input:
33 65 1947.7601065763
output:
60 0.0000000000 0.0000000000 0.0000000000 64.0000000000 1.0000000000 64.0000000000 1.0000000000 0.0000000000 2.0000000000 0.0000000000 2.0000000000 64.0000000000 3.0000000000 64.0000000000 3.0000000000 0.0000000000 4.0000000000 0.0000000000 4.0000000000 64.0000000000 5.0000000000 64.0000000000 5.000...
result:
ok correct
Test #3:
score: 0
Accepted
time: 1ms
memory: 3712kb
input:
51 51 555.0803652025
output:
20 0.0000000000 0.0000000000 0.0000000000 50.0000000000 1.0000000000 50.0000000000 1.0000000000 0.0000000000 2.0000000000 0.0000000000 2.0000000000 50.0000000000 3.0000000000 50.0000000000 3.0000000000 0.0000000000 4.0000000000 0.0000000000 4.0000000000 50.0000000000 5.0000000000 50.0000000000 5.000...
result:
ok correct
Test #4:
score: 0
Accepted
time: 1ms
memory: 3804kb
input:
49 2 67.3588717350
output:
4 0.0000000000 0.0000000000 10.0000000000 0.0000000000 0.9295032889 2.0000000000 49.0000000000 2.0000000000
result:
ok correct
Test #5:
score: 0
Accepted
time: 1ms
memory: 3792kb
input:
37 48 1713.3643608504
output:
72 0.0000000000 0.0000000000 0.0000000000 47.0000000000 1.0000000000 47.0000000000 1.0000000000 0.0000000000 2.0000000000 0.0000000000 2.0000000000 47.0000000000 3.0000000000 47.0000000000 3.0000000000 0.0000000000 4.0000000000 0.0000000000 4.0000000000 47.0000000000 5.0000000000 47.0000000000 5.000...
result:
ok correct
Test #6:
score: 0
Accepted
time: 0ms
memory: 3920kb
input:
51 79 820.1218304546
output:
20 0.0000000000 0.0000000000 0.0000000000 78.0000000000 1.0000000000 78.0000000000 1.0000000000 0.0000000000 2.0000000000 0.0000000000 2.0000000000 78.0000000000 3.0000000000 78.0000000000 3.0000000000 0.0000000000 4.0000000000 0.0000000000 4.0000000000 78.0000000000 5.0000000000 78.0000000000 5.000...
result:
ok correct
Test #7:
score: 0
Accepted
time: 0ms
memory: 3792kb
input:
6 8 37.5338494218
output:
8 0.0000000000 0.0000000000 0.0000000000 7.0000000000 1.0000000000 7.0000000000 1.0000000000 0.0000000000 2.0000000000 0.0000000000 2.0000000000 7.0000000000 6.0000000000 0.8241857523 6.0000000000 8.0000000000
result:
ok correct
Test #8:
score: 0
Accepted
time: 1ms
memory: 3772kb
input:
5 5 7.1908428511
output:
3 0.0000000000 0.0000000000 2.0379095179 2.9620904821 5.0000000000 5.0000000000
result:
ok correct
Test #9:
score: 0
Accepted
time: 0ms
memory: 3860kb
input:
5 4 8.3927665498
output:
3 0.0000000000 0.0000000000 0.6615744220 4.0000000000 5.0000000000 4.0000000000
result:
ok correct
Test #10:
score: 0
Accepted
time: 1ms
memory: 3780kb
input:
4 2 6.4617533647
output:
4 0.0000000000 0.0000000000 1.0000000000 0.0000000000 0.5815523890 2.0000000000 4.0000000000 2.0000000000
result:
ok correct
Test #11:
score: 0
Accepted
time: 2ms
memory: 3924kb
input:
91 87 4830.8473359767
output:
106 0.0000000000 0.0000000000 90.0000000000 0.0000000000 90.0000000000 1.0000000000 0.0000000000 1.0000000000 0.0000000000 2.0000000000 90.0000000000 2.0000000000 90.0000000000 3.0000000000 0.0000000000 3.0000000000 0.0000000000 4.0000000000 90.0000000000 4.0000000000 90.0000000000 5.0000000000 0.00...
result:
ok correct
Test #12:
score: 0
Accepted
time: 2ms
memory: 3896kb
input:
90 90 5088.9280941138
output:
112 0.0000000000 0.0000000000 0.0000000000 89.0000000000 1.0000000000 89.0000000000 1.0000000000 0.0000000000 2.0000000000 0.0000000000 2.0000000000 89.0000000000 3.0000000000 89.0000000000 3.0000000000 0.0000000000 4.0000000000 0.0000000000 4.0000000000 89.0000000000 5.0000000000 89.0000000000 5.00...
result:
ok correct
Test #13:
score: 0
Accepted
time: 0ms
memory: 3804kb
input:
90 92 7004.0153432299
output:
152 0.0000000000 0.0000000000 0.0000000000 91.0000000000 1.0000000000 91.0000000000 1.0000000000 0.0000000000 2.0000000000 0.0000000000 2.0000000000 91.0000000000 3.0000000000 91.0000000000 3.0000000000 0.0000000000 4.0000000000 0.0000000000 4.0000000000 91.0000000000 5.0000000000 91.0000000000 5.00...
result:
ok correct
Test #14:
score: 0
Accepted
time: 1ms
memory: 3976kb
input:
91 83 1879.3819547895
output:
40 0.0000000000 0.0000000000 90.0000000000 0.0000000000 90.0000000000 1.0000000000 0.0000000000 1.0000000000 0.0000000000 2.0000000000 90.0000000000 2.0000000000 90.0000000000 3.0000000000 0.0000000000 3.0000000000 0.0000000000 4.0000000000 90.0000000000 4.0000000000 90.0000000000 5.0000000000 0.000...
result:
ok correct
Test #15:
score: 0
Accepted
time: 1ms
memory: 3676kb
input:
3 81 199.2077743610
output:
4 0.0000000000 0.0000000000 0.0000000000 60.0000000000 3.0000000000 0.9341813816 3.0000000000 81.0000000000
result:
ok correct
Test #16:
score: 0
Accepted
time: 1ms
memory: 3792kb
input:
4 89 288.5915130114
output:
8 0.0000000000 0.0000000000 0.0000000000 88.0000000000 1.0000000000 88.0000000000 1.0000000000 0.0000000000 2.0000000000 0.0000000000 2.0000000000 11.0000000000 4.0000000000 0.2968724823 4.0000000000 89.0000000000
result:
ok correct
Test #17:
score: 0
Accepted
time: 0ms
memory: 3684kb
input:
95 3 175.9210001082
output:
4 0.0000000000 0.0000000000 41.0000000000 0.0000000000 0.5951097381 3.0000000000 95.0000000000 3.0000000000
result:
ok correct
Test #18:
score: 0
Accepted
time: 1ms
memory: 3788kb
input:
84 4 310.3037172015
output:
8 0.0000000000 0.0000000000 83.0000000000 0.0000000000 83.0000000000 1.0000000000 0.0000000000 1.0000000000 0.0000000000 2.0000000000 30.0000000000 2.0000000000 0.8824445294 4.0000000000 84.0000000000 4.0000000000
result:
ok correct
Test #19:
score: 0
Accepted
time: 1ms
memory: 3676kb
input:
2 2 2.8284271248
output:
3 0.0000000000 0.0000000000 0.9999938316 1.0000061684 2.0000000000 2.0000000000
result:
ok correct
Test #20:
score: 0
Accepted
time: 2ms
memory: 3944kb
input:
100 100 10000.0000000000
output:
200 0.0000000000 0.0000000000 0.0000000000 99.0000000000 1.0000000000 99.0000000000 1.0000000000 0.0000000000 2.0000000000 0.0000000000 2.0000000000 99.0000000000 3.0000000000 99.0000000000 3.0000000000 0.0000000000 4.0000000000 0.0000000000 4.0000000000 99.0000000000 5.0000000000 99.0000000000 5.00...
result:
ok correct
Test #21:
score: 0
Accepted
time: 2ms
memory: 3880kb
input:
100 100 9999.2500000000
output:
200 0.0000000000 0.0000000000 0.0000000000 99.0000000000 1.0000000000 99.0000000000 1.0000000000 0.0000000000 2.0000000000 0.0000000000 2.0000000000 99.0000000000 3.0000000000 99.0000000000 3.0000000000 0.0000000000 4.0000000000 0.0000000000 4.0000000000 99.0000000000 5.0000000000 99.0000000000 5.00...
result:
ok correct
Test #22:
score: 0
Accepted
time: 1ms
memory: 3812kb
input:
100 100 2723.8981892905
output:
53 0.0000000000 0.0000000000 0.0000000000 99.0000000000 1.0000000000 99.0000000000 1.0000000000 0.0000000000 2.0000000000 0.0000000000 2.0000000000 99.0000000000 3.0000000000 99.0000000000 3.0000000000 0.0000000000 4.0000000000 0.0000000000 4.0000000000 99.0000000000 5.0000000000 99.0000000000 5.000...
result:
ok correct
Test #23:
score: 0
Accepted
time: 2ms
memory: 3968kb
input:
100 100 8994.4904261819
output:
180 0.0000000000 0.0000000000 0.0000000000 99.0000000000 1.0000000000 99.0000000000 1.0000000000 0.0000000000 2.0000000000 0.0000000000 2.0000000000 99.0000000000 3.0000000000 99.0000000000 3.0000000000 0.0000000000 4.0000000000 0.0000000000 4.0000000000 99.0000000000 5.0000000000 99.0000000000 5.00...
result:
ok correct
Test #24:
score: 0
Accepted
time: 1ms
memory: 3860kb
input:
100 100 881.4998747190
output:
16 0.0000000000 0.0000000000 0.0000000000 99.0000000000 1.0000000000 99.0000000000 1.0000000000 0.0000000000 2.0000000000 0.0000000000 2.0000000000 99.0000000000 3.0000000000 99.0000000000 3.0000000000 0.0000000000 4.0000000000 0.0000000000 4.0000000000 99.0000000000 5.0000000000 99.0000000000 5.000...
result:
ok correct
Test #25:
score: 0
Accepted
time: 2ms
memory: 3984kb
input:
88 94 8266.2500000000
output:
176 0.0000000000 0.0000000000 0.0000000000 93.0000000000 1.0000000000 93.0000000000 1.0000000000 0.0000000000 2.0000000000 0.0000000000 2.0000000000 93.0000000000 3.0000000000 93.0000000000 3.0000000000 0.0000000000 4.0000000000 0.0000000000 4.0000000000 93.0000000000 5.0000000000 93.0000000000 5.00...
result:
ok correct
Test #26:
score: 0
Accepted
time: 0ms
memory: 3860kb
input:
75 37 2772.0000000000
output:
72 0.0000000000 0.0000000000 74.0000000000 0.0000000000 74.0000000000 1.0000000000 0.0000000000 1.0000000000 0.0000000000 2.0000000000 74.0000000000 2.0000000000 74.0000000000 3.0000000000 0.0000000000 3.0000000000 0.0000000000 4.0000000000 74.0000000000 4.0000000000 74.0000000000 5.0000000000 0.000...
result:
ok correct
Test #27:
score: 0
Accepted
time: 1ms
memory: 3672kb
input:
48 39 62.0000000000
output:
3 0.0000000000 0.0000000000 25.3743447637 17.8084987524 48.0000000000 39.0000000000
result:
ok correct
Test #28:
score: 0
Accepted
time: 1ms
memory: 3856kb
input:
98 94 135.9000000000
output:
3 0.0000000000 0.0000000000 50.8577575232 45.0631889651 98.0000000000 94.0000000000
result:
ok correct
Test #29:
score: 0
Accepted
time: 2ms
memory: 3856kb
input:
90 81 7290.0000000000
output:
162 0.0000000000 0.0000000000 89.0000000000 0.0000000000 89.0000000000 1.0000000000 0.0000000000 1.0000000000 0.0000000000 2.0000000000 89.0000000000 2.0000000000 89.0000000000 3.0000000000 0.0000000000 3.0000000000 0.0000000000 4.0000000000 89.0000000000 4.0000000000 89.0000000000 5.0000000000 0.00...
result:
ok correct
Test #30:
score: 0
Accepted
time: 1ms
memory: 3672kb
input:
90 81 121.0826164250
output:
3 0.0000000000 0.0000000000 45.0001902966 40.4997885593 90.0000000000 81.0000000000
result:
ok correct
Test #31:
score: 0
Accepted
time: 1ms
memory: 3800kb
input:
34 99 3366.0000000000
output:
68 0.0000000000 0.0000000000 0.0000000000 98.0000000000 1.0000000000 98.0000000000 1.0000000000 0.0000000000 2.0000000000 0.0000000000 2.0000000000 98.0000000000 3.0000000000 98.0000000000 3.0000000000 0.0000000000 4.0000000000 0.0000000000 4.0000000000 98.0000000000 5.0000000000 98.0000000000 5.000...
result:
ok correct
Test #32:
score: 0
Accepted
time: 0ms
memory: 3664kb
input:
34 99 104.6756896330
output:
3 0.0000000000 0.0000000000 16.9998204617 49.5000616596 34.0000000000 99.0000000000
result:
ok correct
Test #33:
score: 0
Accepted
time: 1ms
memory: 3780kb
input:
3 3 5.9999
output:
3 0.0000000000 0.0000000000 3.0000000000 0.0001000017 3.0000000000 3.0000000000
result:
ok correct
Test #34:
score: 0
Accepted
time: 1ms
memory: 3668kb
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: 3672kb
input:
3 3 6.0001
output:
4 0.0000000000 0.0000000000 0.0000000000 1.0000000000 3.0000000000 0.9999000017 3.0000000000 3.0000000000
result:
ok correct
Test #36:
score: 0
Accepted
time: 1ms
memory: 3724kb
input:
4 4 13.999998
output:
6 0.0000000000 0.0000000000 0.0000000000 3.0000000000 1.0000000000 3.0000000000 1.0000000000 0.0000000000 4.0000000000 0.0000020000 4.0000000000 4.0000000000
result:
ok correct
Test #37:
score: 0
Accepted
time: 1ms
memory: 3748kb
input:
4 4 14.0
output:
6 0.0000000000 0.0000000000 0.0000000000 3.0000000000 1.0000000000 3.0000000000 1.0000000000 0.0000000000 4.0000000000 0.0000000000 4.0000000000 4.0000000000
result:
ok correct
Test #38:
score: 0
Accepted
time: 1ms
memory: 3672kb
input:
4 4 14.000002
output:
8 0.0000000000 0.0000000000 0.0000000000 3.0000000000 1.0000000000 3.0000000000 1.0000000000 0.0000000000 2.0000000000 0.0000000000 2.0000000000 1.0000000000 4.0000000000 0.9999980000 4.0000000000 4.0000000000
result:
ok correct
Test #39:
score: 0
Accepted
time: 0ms
memory: 3748kb
input:
4 4 15.123104
output:
8 0.0000000000 0.0000000000 0.0000000000 3.0000000000 1.0000000000 3.0000000000 1.0000000000 0.0000000000 2.0000000000 0.0000000000 2.0000000000 1.0000000000 4.0000000000 0.0788365365 4.0000000000 4.0000000000
result:
ok correct
Test #40:
score: 0
Accepted
time: 1ms
memory: 3852kb
input:
4 4 15.123106
output:
8 0.0000000000 0.0000000000 0.0000000000 3.0000000000 1.0000000000 3.0000000000 1.0000000000 0.0000000000 2.0000000000 0.0000000000 2.0000000000 1.0000000000 4.0000000000 0.0788351264 4.0000000000 4.0000000000
result:
ok correct
Test #41:
score: 0
Accepted
time: 0ms
memory: 3664kb
input:
4 4 15.123108
output:
8 0.0000000000 0.0000000000 0.0000000000 3.0000000000 1.0000000000 3.0000000000 1.0000000000 0.0000000000 2.0000000000 0.0000000000 2.0000000000 1.0000000000 4.0000000000 0.0788337163 4.0000000000 4.0000000000
result:
ok correct
Test #42:
score: 0
Accepted
time: 1ms
memory: 3748kb
input:
4 4 14.593385
output:
8 0.0000000000 0.0000000000 0.0000000000 3.0000000000 1.0000000000 3.0000000000 1.0000000000 0.0000000000 2.0000000000 0.0000000000 2.0000000000 1.0000000000 4.0000000000 0.4745003618 4.0000000000 4.0000000000
result:
ok correct
Test #43:
score: 0
Accepted
time: 1ms
memory: 3752kb
input:
4 4 14.593387
output:
8 0.0000000000 0.0000000000 0.0000000000 3.0000000000 1.0000000000 3.0000000000 1.0000000000 0.0000000000 2.0000000000 0.0000000000 2.0000000000 1.0000000000 4.0000000000 0.4744987671 4.0000000000 4.0000000000
result:
ok correct
Test #44:
score: 0
Accepted
time: 1ms
memory: 3780kb
input:
4 4 14.593389
output:
8 0.0000000000 0.0000000000 0.0000000000 3.0000000000 1.0000000000 3.0000000000 1.0000000000 0.0000000000 2.0000000000 0.0000000000 2.0000000000 1.0000000000 4.0000000000 0.4744971724 4.0000000000 4.0000000000
result:
ok correct
Test #45:
score: 0
Accepted
time: 1ms
memory: 3780kb
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: 1ms
memory: 3720kb
input:
3 3 5.0
output:
3 0.0000000000 0.0000000000 3.0000000000 1.2500000000 3.0000000000 3.0000000000
result:
ok correct
Test #47:
score: 0
Accepted
time: 1ms
memory: 3664kb
input:
4 4 15.123
output:
8 0.0000000000 0.0000000000 0.0000000000 3.0000000000 1.0000000000 3.0000000000 1.0000000000 0.0000000000 2.0000000000 0.0000000000 2.0000000000 1.0000000000 4.0000000000 0.0789098623 4.0000000000 4.0000000000
result:
ok correct
Test #48:
score: 0
Accepted
time: 1ms
memory: 3676kb
input:
4 4 14.1
output:
8 0.0000000000 0.0000000000 0.0000000000 3.0000000000 1.0000000000 3.0000000000 1.0000000000 0.0000000000 2.0000000000 0.0000000000 2.0000000000 1.0000000000 4.0000000000 0.9023809524 4.0000000000 4.0000000000
result:
ok correct
Test #49:
score: 0
Accepted
time: 2ms
memory: 3860kb
input:
3 3 9.0
output:
6 0.0000000000 0.0000000000 0.0000000000 2.0000000000 1.0000000000 2.0000000000 1.0000000000 1.0000000000 3.0000000000 0.1666666667 3.0000000000 3.0000000000
result:
ok correct
Test #50:
score: 0
Accepted
time: 1ms
memory: 3792kb
input:
4 4 16.0
output:
8 0.0000000000 0.0000000000 0.0000000000 3.0000000000 1.0000000000 3.0000000000 1.0000000000 0.0000000000 2.0000000000 0.0000000000 2.0000000000 2.0000000000 4.0000000000 0.5000000000 4.0000000000 4.0000000000
result:
ok correct