QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#33149 | #2290. Kinking Cables | YaoBIG# | AC ✓ | 3ms | 3864kb | C++17 | 5.4kb | 2022-05-28 23:29:44 | 2022-05-28 23:29:45 |
Judging History
answer
#include "bits/stdc++.h"
#define rep(i, a, n) for(auto i = a; i <= (n); i++)
#define per(i, a, n) for(auto i = n; i >= (a); i--)
#define pb push_back
#define mp make_pair
#define FI first
#define SE second
#define all(a) a.begin(), a.end()
#define sz(a) (int)(a).size()
template<class T> inline bool chmax(T &a, T b) { if(a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T &a, T b) { if(b < a) { a = b; return 1; } return 0; }
using namespace std;
template<class A, class B> string to_string(pair<A, B> p);
string to_string(const string &s) { return '"' + s + '"'; }
string to_string(const char *s) { return to_string((string) s); }
string to_string(char c) { return "'" + string(1, c) + "'"; }
string to_string(bool x) { return x ? "true" : "false"; }
template<class A> string to_string(A v)
{
bool first = 1;
string res = "{";
for(const auto &x: v)
{
if (!first) res += ", ";
first = 0;
res += to_string(x);
}
res += "}";
return res;
}
template<class A, class B> string to_string(pair<A, B> p) { return "(" + to_string(p.FI) + ", " + to_string(p.SE) + ")"; }
void debug_out() { cerr << endl; }
template<class Head, class... Tail> void debug_out(Head H, Tail... T)
{
cerr << " " << to_string(H);
debug_out(T...);
}
#ifndef ONLINE_JUDGE
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) if(0) puts("No effect.")
#endif
using ll = long long;
// using LL = __int128;
using pii = pair<int, int>;
using vi = vector<int>;
using vvi = vector<vi>;
using db = double;
using ldb = long double;
const int maxn = 1'000'000;
const int inf = 0x3f3f3f3f;
const int mod = 1e9 + 7;
const db pi = acos(-1.0);
template<class T> struct TPoint
{ // use T = double or T = long long.
using P = TPoint;
static constexpr T eps = static_cast<T>(1e-9);
static int sgn(T x) { return (x > eps) - (x < -eps); }
static int cmp(T x, T y) { return sgn(x - y); }
static T sqr(T x) { return x * x; }
T x, y;
P operator +(P a) const { return P{x + a.x, y + a.y}; }
P operator -(P a) const { return P{x - a.x, y - a.y}; }
P operator *(T a) const { return P{x * a, y * a}; }
P operator /(T a) const { return P{x / a, y / a}; }
bool operator ==(P a) const { return cmp(x, a.x) == 0 && cmp(y, a.y) == 0; }
bool operator <(P a) const { return cmp(x, a.x) == 0 ? cmp(y, a.y) < 0: x < a.x; }
T len() const { return sqrt(sqr(x) + sqr(y)); }
T dis_to(P a) const { return (*this - a).len(); }
T len2() const { return sqr(x) + sqr(y); }
P unit() const { return *this / len(); }
T dot(P b) const { return x * b.x + y * b.y; }
T cross(P b) const { return x * b.y - y * b.x; }
bool is_upper() const { return y > eps || (sgn(y) == 0 && x < -eps); }
static bool cmp_polar(P a, P b)
{
if(a.is_upper() != b.is_upper()) return a.is_upper() < b.is_upper();
return a.cross(b) > eps;
// one issue of this function is that if you use float-type and the values have large range then colinear points might be viewed as non-colinear.
}
P rot90() { return P{-y, x}; }
// the following only work for double
P rotate(db theta) const
{
P a{cos(theta), sin(theta)};
return P{x * a.x - y * a.y, x * a.y + y * a.x};
}
T project_len(P a, P b) const { return (*this - a).dot((b - a).unit()); } // signed.
T dis_to_line(P a, P b) const { return (*this - a).cross((b - a).unit()); } // signed.
T dis_to_seg(P a, P b) const
{
if(project_len(a, b) < -eps) return (*this - a).len();
if(project_len(b, a) < -eps) return (*this - b).len();
return fabs(dis_to_line(a, b));
}
P project_to_line(P a, P b) const { return a + (b - a) * project_len(a, b); }
bool on_seg(P a, P b) const { return dis_to_seg(a, b) <= eps; } // including vertice a and b.
bool on_line(P a, P b) const { return sgn(dis_to_line(a, b)) == 0; }
};
using P = TPoint<db>;
using vp = vector<P>;
int main()
{
ios::sync_with_stdio(0); cin.tie(0);
int n, m; db L;
cin >> n >> m >> L;
auto cal = [&](const vp &A)
{
db res = 0;
rep(i, 0, sz(A) - 2) res += (A[i] - A[i + 1]).len();
return res;
};
if(L <= n + m)
{
P md{n / 2.0, m / 2.0}, cor{n, 0};
auto get = [&](db rat) { return vp{P{0, 0}, md + (cor - md) * rat, P{n, m}}; };
db l = 0.0, r = 1.0;
rep(_, 1, 60)
{
db mid = (l + r) / 2.0;
if(cal(get(mid)) >= L) r = mid;
else l = mid;
}
vp ans = get(r);
printf("%d\n", sz(ans));
for(auto [x, y]: ans) printf("%.9f %.9f\n", x, y);
}
else
{
auto get = [&](db rat)
{
vp res{P{0, 0}};
rep(i, 0, m - 1)
{
if(i & 1) res.pb(P{n * (1 - rat), i});
else res.pb(P{n, i});
}
res.pb(P{n, m});
return res;
};
db l = 0.0, r = 1.0;
rep(_, 1, 60)
{
db mid = (l + r) / 2.0;
if(cal(get(mid)) >= L) r = mid;
else l = mid;
}
vp ans = get(r);
printf("%d\n", sz(ans));
for(auto [x, y]: ans) printf("%.9f %.9f\n", x, y);
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3688kb
input:
79 78 1980.7712136406
output:
80 0.000000000 0.000000000 79.000000000 0.000000000 54.638833604 1.000000000 79.000000000 2.000000000 54.638833604 3.000000000 79.000000000 4.000000000 54.638833604 5.000000000 79.000000000 6.000000000 54.638833604 7.000000000 79.000000000 8.000000000 54.638833604 9.000000000 79.000000000 10.0000000...
result:
ok correct
Test #2:
score: 0
Accepted
time: 2ms
memory: 3812kb
input:
33 65 1947.7601065763
output:
67 0.000000000 0.000000000 33.000000000 0.000000000 3.114224021 1.000000000 33.000000000 2.000000000 3.114224021 3.000000000 33.000000000 4.000000000 3.114224021 5.000000000 33.000000000 6.000000000 3.114224021 7.000000000 33.000000000 8.000000000 3.114224021 9.000000000 33.000000000 10.000000000 3....
result:
ok correct
Test #3:
score: 0
Accepted
time: 2ms
memory: 3820kb
input:
51 51 555.0803652025
output:
53 0.000000000 0.000000000 51.000000000 0.000000000 40.988209873 1.000000000 51.000000000 2.000000000 40.988209873 3.000000000 51.000000000 4.000000000 40.988209873 5.000000000 51.000000000 6.000000000 40.988209873 7.000000000 51.000000000 8.000000000 40.988209873 9.000000000 51.000000000 10.0000000...
result:
ok correct
Test #4:
score: 0
Accepted
time: 2ms
memory: 3776kb
input:
49 2 67.3588717350
output:
4 0.000000000 0.000000000 49.000000000 0.000000000 39.875196285 1.000000000 49.000000000 2.000000000
result:
ok correct
Test #5:
score: 0
Accepted
time: 2ms
memory: 3748kb
input:
37 48 1713.3643608504
output:
50 0.000000000 0.000000000 37.000000000 0.000000000 2.090062115 1.000000000 37.000000000 2.000000000 2.090062115 3.000000000 37.000000000 4.000000000 2.090062115 5.000000000 37.000000000 6.000000000 2.090062115 7.000000000 37.000000000 8.000000000 2.090062115 9.000000000 37.000000000 10.000000000 2....
result:
ok correct
Test #6:
score: 0
Accepted
time: 2ms
memory: 3796kb
input:
51 79 820.1218304546
output:
81 0.000000000 0.000000000 51.000000000 0.000000000 41.203188989 1.000000000 51.000000000 2.000000000 41.203188989 3.000000000 51.000000000 4.000000000 41.203188989 5.000000000 51.000000000 6.000000000 41.203188989 7.000000000 51.000000000 8.000000000 41.203188989 9.000000000 51.000000000 10.0000000...
result:
ok correct
Test #7:
score: 0
Accepted
time: 2ms
memory: 3780kb
input:
6 8 37.5338494218
output:
10 0.000000000 0.000000000 6.000000000 0.000000000 2.187226118 1.000000000 6.000000000 2.000000000 2.187226118 3.000000000 6.000000000 4.000000000 2.187226118 5.000000000 6.000000000 6.000000000 2.187226118 7.000000000 6.000000000 8.000000000
result:
ok correct
Test #8:
score: 0
Accepted
time: 1ms
memory: 3684kb
input:
5 5 7.1908428511
output:
3 0.000000000 0.000000000 2.962090482 2.037909518 5.000000000 5.000000000
result:
ok correct
Test #9:
score: 0
Accepted
time: 2ms
memory: 3740kb
input:
5 4 8.3927665498
output:
3 0.000000000 0.000000000 4.648738548 0.281009162 5.000000000 4.000000000
result:
ok correct
Test #10:
score: 0
Accepted
time: 0ms
memory: 3796kb
input:
4 2 6.4617533647
output:
4 0.000000000 0.000000000 4.000000000 0.000000000 3.282324999 1.000000000 4.000000000 2.000000000
result:
ok correct
Test #11:
score: 0
Accepted
time: 0ms
memory: 3668kb
input:
91 87 4830.8473359767
output:
89 0.000000000 0.000000000 91.000000000 0.000000000 35.906198684 1.000000000 91.000000000 2.000000000 35.906198684 3.000000000 91.000000000 4.000000000 35.906198684 5.000000000 91.000000000 6.000000000 35.906198684 7.000000000 91.000000000 8.000000000 35.906198684 9.000000000 91.000000000 10.0000000...
result:
ok correct
Test #12:
score: 0
Accepted
time: 0ms
memory: 3744kb
input:
90 90 5088.9280941138
output:
92 0.000000000 0.000000000 90.000000000 0.000000000 34.465357169 1.000000000 90.000000000 2.000000000 34.465357169 3.000000000 90.000000000 4.000000000 34.465357169 5.000000000 90.000000000 6.000000000 34.465357169 7.000000000 90.000000000 8.000000000 34.465357169 9.000000000 90.000000000 10.0000000...
result:
ok correct
Test #13:
score: 0
Accepted
time: 2ms
memory: 3692kb
input:
90 92 7004.0153432299
output:
94 0.000000000 0.000000000 90.000000000 0.000000000 14.854312760 1.000000000 90.000000000 2.000000000 14.854312760 3.000000000 90.000000000 4.000000000 14.854312760 5.000000000 90.000000000 6.000000000 14.854312760 7.000000000 90.000000000 8.000000000 14.854312760 9.000000000 90.000000000 10.0000000...
result:
ok correct
Test #14:
score: 0
Accepted
time: 2ms
memory: 3780kb
input:
91 83 1879.3819547895
output:
85 0.000000000 0.000000000 91.000000000 0.000000000 69.225609748 1.000000000 91.000000000 2.000000000 69.225609748 3.000000000 91.000000000 4.000000000 69.225609748 5.000000000 91.000000000 6.000000000 69.225609748 7.000000000 91.000000000 8.000000000 69.225609748 9.000000000 91.000000000 10.0000000...
result:
ok correct
Test #15:
score: 0
Accepted
time: 2ms
memory: 3688kb
input:
3 81 199.2077743610
output:
83 0.000000000 0.000000000 3.000000000 0.000000000 0.774225024 1.000000000 3.000000000 2.000000000 0.774225024 3.000000000 3.000000000 4.000000000 0.774225024 5.000000000 3.000000000 6.000000000 0.774225024 7.000000000 3.000000000 8.000000000 0.774225024 9.000000000 3.000000000 10.000000000 0.774225...
result:
ok correct
Test #16:
score: 0
Accepted
time: 2ms
memory: 3776kb
input:
4 89 288.5915130114
output:
91 0.000000000 0.000000000 4.000000000 0.000000000 0.936448227 1.000000000 4.000000000 2.000000000 0.936448227 3.000000000 4.000000000 4.000000000 0.936448227 5.000000000 4.000000000 6.000000000 0.936448227 7.000000000 4.000000000 8.000000000 0.936448227 9.000000000 4.000000000 10.000000000 0.936448...
result:
ok correct
Test #17:
score: 0
Accepted
time: 3ms
memory: 3688kb
input:
95 3 175.9210001082
output:
5 0.000000000 0.000000000 95.000000000 0.000000000 55.052014261 1.000000000 95.000000000 2.000000000 95.000000000 3.000000000
result:
ok correct
Test #18:
score: 0
Accepted
time: 3ms
memory: 3796kb
input:
84 4 310.3037172015
output:
6 0.000000000 0.000000000 84.000000000 0.000000000 27.432909071 1.000000000 84.000000000 2.000000000 27.432909071 3.000000000 84.000000000 4.000000000
result:
ok correct
Test #19:
score: 0
Accepted
time: 0ms
memory: 3824kb
input:
2 2 2.8284271248
output:
3 0.000000000 0.000000000 1.000006168 0.999993832 2.000000000 2.000000000
result:
ok correct
Test #20:
score: 0
Accepted
time: 1ms
memory: 3696kb
input:
100 100 10000.0000000000
output:
102 0.000000000 0.000000000 100.000000000 0.000000000 1.005050634 1.000000000 100.000000000 2.000000000 1.005050634 3.000000000 100.000000000 4.000000000 1.005050634 5.000000000 100.000000000 6.000000000 1.005050634 7.000000000 100.000000000 8.000000000 1.005050634 9.000000000 100.000000000 10.00000...
result:
ok correct
Test #21:
score: 0
Accepted
time: 0ms
memory: 3792kb
input:
100 100 9999.2500000000
output:
102 0.000000000 0.000000000 100.000000000 0.000000000 1.012551017 1.000000000 100.000000000 2.000000000 1.012551017 3.000000000 100.000000000 4.000000000 1.012551017 5.000000000 100.000000000 6.000000000 1.012551017 7.000000000 100.000000000 8.000000000 1.012551017 9.000000000 100.000000000 10.00000...
result:
ok correct
Test #22:
score: 0
Accepted
time: 2ms
memory: 3768kb
input:
100 100 2723.8981892905
output:
102 0.000000000 0.000000000 100.000000000 0.000000000 73.780080649 1.000000000 100.000000000 2.000000000 73.780080649 3.000000000 100.000000000 4.000000000 73.780080649 5.000000000 100.000000000 6.000000000 73.780080649 7.000000000 100.000000000 8.000000000 73.780080649 9.000000000 100.000000000 10....
result:
ok correct
Test #23:
score: 0
Accepted
time: 2ms
memory: 3820kb
input:
100 100 8994.4904261819
output:
102 0.000000000 0.000000000 100.000000000 0.000000000 11.060717373 1.000000000 100.000000000 2.000000000 11.060717373 3.000000000 100.000000000 4.000000000 11.060717373 5.000000000 100.000000000 6.000000000 11.060717373 7.000000000 100.000000000 8.000000000 11.060717373 9.000000000 100.000000000 10....
result:
ok correct
Test #24:
score: 0
Accepted
time: 0ms
memory: 3824kb
input:
100 100 881.4998747190
output:
102 0.000000000 0.000000000 100.000000000 0.000000000 92.249244848 1.000000000 100.000000000 2.000000000 92.249244848 3.000000000 100.000000000 4.000000000 92.249244848 5.000000000 100.000000000 6.000000000 92.249244848 7.000000000 100.000000000 8.000000000 92.249244848 9.000000000 100.000000000 10....
result:
ok correct
Test #25:
score: 0
Accepted
time: 2ms
memory: 3792kb
input:
88 94 8266.2500000000
output:
96 0.000000000 0.000000000 88.000000000 0.000000000 1.003087566 1.000000000 88.000000000 2.000000000 1.003087566 3.000000000 88.000000000 4.000000000 1.003087566 5.000000000 88.000000000 6.000000000 1.003087566 7.000000000 88.000000000 8.000000000 1.003087566 9.000000000 88.000000000 10.000000000 1....
result:
ok correct
Test #26:
score: 0
Accepted
time: 0ms
memory: 3688kb
input:
75 37 2772.0000000000
output:
39 0.000000000 0.000000000 75.000000000 0.000000000 0.117787967 1.000000000 75.000000000 2.000000000 0.117787967 3.000000000 75.000000000 4.000000000 0.117787967 5.000000000 75.000000000 6.000000000 0.117787967 7.000000000 75.000000000 8.000000000 0.117787967 9.000000000 75.000000000 10.000000000 0....
result:
ok correct
Test #27:
score: 0
Accepted
time: 2ms
memory: 3800kb
input:
48 39 62.0000000000
output:
3 0.000000000 0.000000000 25.727909464 18.096073560 48.000000000 39.000000000
result:
ok correct
Test #28:
score: 0
Accepted
time: 2ms
memory: 3792kb
input:
98 94 135.9000000000
output:
3 0.000000000 0.000000000 50.938490397 45.140631660 98.000000000 94.000000000
result:
ok correct
Test #29:
score: 0
Accepted
time: 1ms
memory: 3864kb
input:
90 81 7290.0000000000
output:
83 0.000000000 0.000000000 90.000000000 0.000000000 0.018056499 1.000000000 90.000000000 2.000000000 0.018056499 3.000000000 90.000000000 4.000000000 0.018056499 5.000000000 90.000000000 6.000000000 0.018056499 7.000000000 90.000000000 8.000000000 0.018056499 9.000000000 90.000000000 10.000000000 0....
result:
ok correct
Test #30:
score: 0
Accepted
time: 2ms
memory: 3860kb
input:
90 81 121.0826164250
output:
3 0.000000000 0.000000000 45.000212614 40.499808647 90.000000000 81.000000000
result:
ok correct
Test #31:
score: 0
Accepted
time: 2ms
memory: 3800kb
input:
34 99 3366.0000000000
output:
101 0.000000000 0.000000000 34.000000000 0.000000000 0.024917563 1.000000000 34.000000000 2.000000000 0.024917563 3.000000000 34.000000000 4.000000000 0.024917563 5.000000000 34.000000000 6.000000000 0.024917563 7.000000000 34.000000000 8.000000000 0.024917563 9.000000000 34.000000000 10.000000000 0...
result:
ok correct
Test #32:
score: 0
Accepted
time: 2ms
memory: 3780kb
input:
34 99 104.6756896330
output:
3 0.000000000 0.000000000 17.000100357 49.499707784 34.000000000 99.000000000
result:
ok correct
Test #33:
score: 0
Accepted
time: 2ms
memory: 3780kb
input:
3 3 5.9999
output:
3 0.000000000 0.000000000 2.999950000 0.000050000 3.000000000 3.000000000
result:
ok correct
Test #34:
score: 0
Accepted
time: 2ms
memory: 3744kb
input:
3 3 6.0
output:
3 0.000000000 0.000000000 3.000000000 0.000000000 3.000000000 3.000000000
result:
ok correct
Test #35:
score: 0
Accepted
time: 3ms
memory: 3692kb
input:
3 3 6.0001
output:
5 0.000000000 0.000000000 3.000000000 0.000000000 2.989999875 1.000000000 3.000000000 2.000000000 3.000000000 3.000000000
result:
ok correct
Test #36:
score: 0
Accepted
time: 2ms
memory: 3784kb
input:
4 4 13.999998
output:
6 0.000000000 0.000000000 4.000000000 0.000000000 1.708712698 1.000000000 4.000000000 2.000000000 1.708712698 3.000000000 4.000000000 4.000000000
result:
ok correct
Test #37:
score: 0
Accepted
time: 2ms
memory: 3776kb
input:
4 4 14.0
output:
6 0.000000000 0.000000000 4.000000000 0.000000000 1.708712153 1.000000000 4.000000000 2.000000000 1.708712153 3.000000000 4.000000000 4.000000000
result:
ok correct
Test #38:
score: 0
Accepted
time: 2ms
memory: 3816kb
input:
4 4 14.000002
output:
6 0.000000000 0.000000000 4.000000000 0.000000000 1.708711607 1.000000000 4.000000000 2.000000000 1.708711607 3.000000000 4.000000000 4.000000000
result:
ok correct
Test #39:
score: 0
Accepted
time: 2ms
memory: 3668kb
input:
4 4 15.123104
output:
6 0.000000000 0.000000000 4.000000000 0.000000000 1.405252390 1.000000000 4.000000000 2.000000000 1.405252390 3.000000000 4.000000000 4.000000000
result:
ok correct
Test #40:
score: 0
Accepted
time: 2ms
memory: 3780kb
input:
4 4 15.123106
output:
6 0.000000000 0.000000000 4.000000000 0.000000000 1.405251854 1.000000000 4.000000000 2.000000000 1.405251854 3.000000000 4.000000000 4.000000000
result:
ok correct
Test #41:
score: 0
Accepted
time: 2ms
memory: 3688kb
input:
4 4 15.123108
output:
6 0.000000000 0.000000000 4.000000000 0.000000000 1.405251318 1.000000000 4.000000000 2.000000000 1.405251318 3.000000000 4.000000000 4.000000000
result:
ok correct
Test #42:
score: 0
Accepted
time: 2ms
memory: 3780kb
input:
4 4 14.593385
output:
6 0.000000000 0.000000000 4.000000000 0.000000000 1.547707632 1.000000000 4.000000000 2.000000000 1.547707632 3.000000000 4.000000000 4.000000000
result:
ok correct
Test #43:
score: 0
Accepted
time: 2ms
memory: 3784kb
input:
4 4 14.593387
output:
6 0.000000000 0.000000000 4.000000000 0.000000000 1.547707092 1.000000000 4.000000000 2.000000000 1.547707092 3.000000000 4.000000000 4.000000000
result:
ok correct
Test #44:
score: 0
Accepted
time: 2ms
memory: 3824kb
input:
4 4 14.593389
output:
6 0.000000000 0.000000000 4.000000000 0.000000000 1.547706552 1.000000000 4.000000000 2.000000000 1.547706552 3.000000000 4.000000000 4.000000000
result:
ok correct
Test #45:
score: 0
Accepted
time: 0ms
memory: 3684kb
input:
2 2 4.0
output:
3 0.000000000 0.000000000 2.000000000 0.000000000 2.000000000 2.000000000
result:
ok correct
Test #46:
score: 0
Accepted
time: 2ms
memory: 3696kb
input:
3 3 5.0
output:
3 0.000000000 0.000000000 2.435414347 0.564585653 3.000000000 3.000000000
result:
ok correct
Test #47:
score: 0
Accepted
time: 2ms
memory: 3684kb
input:
4 4 15.123
output:
6 0.000000000 0.000000000 4.000000000 0.000000000 1.405280254 1.000000000 4.000000000 2.000000000 1.405280254 3.000000000 4.000000000 4.000000000
result:
ok correct
Test #48:
score: 0
Accepted
time: 2ms
memory: 3684kb
input:
4 4 14.1
output:
6 0.000000000 0.000000000 4.000000000 0.000000000 1.681460589 1.000000000 4.000000000 2.000000000 1.681460589 3.000000000 4.000000000 4.000000000
result:
ok correct
Test #49:
score: 0
Accepted
time: 2ms
memory: 3784kb
input:
3 3 9.0
output:
5 0.000000000 0.000000000 3.000000000 0.000000000 0.708712153 1.000000000 3.000000000 2.000000000 3.000000000 3.000000000
result:
ok correct
Test #50:
score: 0
Accepted
time: 2ms
memory: 3688kb
input:
4 4 16.0
output:
6 0.000000000 0.000000000 4.000000000 0.000000000 1.171572875 1.000000000 4.000000000 2.000000000 1.171572875 3.000000000 4.000000000 4.000000000
result:
ok correct