QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#134438 | #2290. Kinking Cables | Yarema# | AC ✓ | 1ms | 3848kb | C++17 | 1.8kb | 2023-08-03 19:45:31 | 2023-08-03 19:45:33 |
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;
const int INF = 1e9 + 7;
const double EPS = 1e-6;
struct point
{
double x, y;
point() {}
point(double a, double b): x(a), y(b) {};
point operator +(const point& p) const
{
return point(x + p.x, y + p.y);
}
point operator -(const point& p) const
{
return point(x - p.x, y - p.y);
}
point operator *(double d) const
{
return point(x * d, y * d);
}
double d2()
{
return sqrt(x * x + y * y);
}
};
double dis(point a, point b)
{
a = a - b;
return a.d2();
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int n, m;
cin >> n >> m;
double l;
cin >> l;
vector<point> ans;
int j = 0;
point a(0, 0);
ans.PB(a);
point b(n, 0);
point c(0, 1);
point d(n, m);
while (dis(a, b) + dis(b, c) + dis(c, d) < l)
{
ans.PB(b);
ans.PB(c);
a.y += 1;
b.y += 1;
c.y += 1;
l -= dis(a, b) + dis(b, c);
j++;
}
assert(l + EPS > dis(a, d));
double L = 0, R = 1;
point v1(n, 0);
point v2(-n, 0);
FOR (i, 0, 100)
{
double M = (L + R) / 2;
b = a + v1 * M;
c = d + v2 * M;
double ds = dis(a, b) + dis(b, c) + dis(c, d);
if (ds < l)
L = M;
else
R = M;
}
ans.PB(a + v1 * L);
ans.PB(d + v2 * L);
ans.PB(d);
cout << fixed << setprecision(7) << SZ(ans) << '\n';
for (auto p : ans)
cout << p.x << ' ' << p.y << '\n';
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 3776kb
input:
79 78 1980.7712136406
output:
26 0.0000000 0.0000000 79.0000000 0.0000000 0.0000000 1.0000000 79.0000000 1.0000000 0.0000000 2.0000000 79.0000000 2.0000000 0.0000000 3.0000000 79.0000000 3.0000000 0.0000000 4.0000000 79.0000000 4.0000000 0.0000000 5.0000000 79.0000000 5.0000000 0.0000000 6.0000000 79.0000000 6.0000000 0.0000000 ...
result:
ok correct
Test #2:
score: 0
Accepted
time: 1ms
memory: 3848kb
input:
33 65 1947.7601065763
output:
60 0.0000000 0.0000000 33.0000000 0.0000000 0.0000000 1.0000000 33.0000000 1.0000000 0.0000000 2.0000000 33.0000000 2.0000000 0.0000000 3.0000000 33.0000000 3.0000000 0.0000000 4.0000000 33.0000000 4.0000000 0.0000000 5.0000000 33.0000000 5.0000000 0.0000000 6.0000000 33.0000000 6.0000000 0.0000000 ...
result:
ok correct
Test #3:
score: 0
Accepted
time: 1ms
memory: 3728kb
input:
51 51 555.0803652025
output:
12 0.0000000 0.0000000 51.0000000 0.0000000 0.0000000 1.0000000 51.0000000 1.0000000 0.0000000 2.0000000 51.0000000 2.0000000 0.0000000 3.0000000 51.0000000 3.0000000 0.0000000 4.0000000 43.7601491 4.0000000 7.2398509 51.0000000 51.0000000 51.0000000
result:
ok correct
Test #4:
score: 0
Accepted
time: 1ms
memory: 3832kb
input:
49 2 67.3588717350
output:
4 0.0000000 0.0000000 29.0352484 0.0000000 19.9647516 2.0000000 49.0000000 2.0000000
result:
ok correct
Test #5:
score: 0
Accepted
time: 1ms
memory: 3652kb
input:
37 48 1713.3643608504
output:
48 0.0000000 0.0000000 37.0000000 0.0000000 0.0000000 1.0000000 37.0000000 1.0000000 0.0000000 2.0000000 37.0000000 2.0000000 0.0000000 3.0000000 37.0000000 3.0000000 0.0000000 4.0000000 37.0000000 4.0000000 0.0000000 5.0000000 37.0000000 5.0000000 0.0000000 6.0000000 37.0000000 6.0000000 0.0000000 ...
result:
ok correct
Test #6:
score: 0
Accepted
time: 1ms
memory: 3656kb
input:
51 79 820.1218304546
output:
18 0.0000000 0.0000000 51.0000000 0.0000000 0.0000000 1.0000000 51.0000000 1.0000000 0.0000000 2.0000000 51.0000000 2.0000000 0.0000000 3.0000000 51.0000000 3.0000000 0.0000000 4.0000000 51.0000000 4.0000000 0.0000000 5.0000000 51.0000000 5.0000000 0.0000000 6.0000000 51.0000000 6.0000000 0.0000000 ...
result:
ok correct
Test #7:
score: 0
Accepted
time: 0ms
memory: 3836kb
input:
6 8 37.5338494218
output:
8 0.0000000 0.0000000 6.0000000 0.0000000 0.0000000 1.0000000 6.0000000 1.0000000 0.0000000 2.0000000 3.6206365 2.0000000 2.3793635 8.0000000 6.0000000 8.0000000
result:
ok correct
Test #8:
score: 0
Accepted
time: 1ms
memory: 3652kb
input:
5 5 7.1908428511
output:
4 0.0000000 0.0000000 0.1949274 0.0000000 4.8050726 5.0000000 5.0000000 5.0000000
result:
ok correct
Test #9:
score: 0
Accepted
time: 1ms
memory: 3784kb
input:
5 4 8.3927665498
output:
4 0.0000000 0.0000000 2.1692128 0.0000000 2.8307872 4.0000000 5.0000000 4.0000000
result:
ok correct
Test #10:
score: 0
Accepted
time: 1ms
memory: 3760kb
input:
4 2 6.4617533647
output:
4 0.0000000 0.0000000 2.2092238 0.0000000 1.7907762 2.0000000 4.0000000 2.0000000
result:
ok correct
Test #11:
score: 0
Accepted
time: 0ms
memory: 3652kb
input:
91 87 4830.8473359767
output:
54 0.0000000 0.0000000 91.0000000 0.0000000 0.0000000 1.0000000 91.0000000 1.0000000 0.0000000 2.0000000 91.0000000 2.0000000 0.0000000 3.0000000 91.0000000 3.0000000 0.0000000 4.0000000 91.0000000 4.0000000 0.0000000 5.0000000 91.0000000 5.0000000 0.0000000 6.0000000 91.0000000 6.0000000 0.0000000 ...
result:
ok correct
Test #12:
score: 0
Accepted
time: 1ms
memory: 3596kb
input:
90 90 5088.9280941138
output:
58 0.0000000 0.0000000 90.0000000 0.0000000 0.0000000 1.0000000 90.0000000 1.0000000 0.0000000 2.0000000 90.0000000 2.0000000 0.0000000 3.0000000 90.0000000 3.0000000 0.0000000 4.0000000 90.0000000 4.0000000 0.0000000 5.0000000 90.0000000 5.0000000 0.0000000 6.0000000 90.0000000 6.0000000 0.0000000 ...
result:
ok correct
Test #13:
score: 0
Accepted
time: 1ms
memory: 3848kb
input:
90 92 7004.0153432299
output:
80 0.0000000 0.0000000 90.0000000 0.0000000 0.0000000 1.0000000 90.0000000 1.0000000 0.0000000 2.0000000 90.0000000 2.0000000 0.0000000 3.0000000 90.0000000 3.0000000 0.0000000 4.0000000 90.0000000 4.0000000 0.0000000 5.0000000 90.0000000 5.0000000 0.0000000 6.0000000 90.0000000 6.0000000 0.0000000 ...
result:
ok correct
Test #14:
score: 0
Accepted
time: 1ms
memory: 3840kb
input:
91 83 1879.3819547895
output:
22 0.0000000 0.0000000 91.0000000 0.0000000 0.0000000 1.0000000 91.0000000 1.0000000 0.0000000 2.0000000 91.0000000 2.0000000 0.0000000 3.0000000 91.0000000 3.0000000 0.0000000 4.0000000 91.0000000 4.0000000 0.0000000 5.0000000 91.0000000 5.0000000 0.0000000 6.0000000 91.0000000 6.0000000 0.0000000 ...
result:
ok correct
Test #15:
score: 0
Accepted
time: 0ms
memory: 3844kb
input:
3 81 199.2077743610
output:
48 0.0000000 0.0000000 3.0000000 0.0000000 0.0000000 1.0000000 3.0000000 1.0000000 0.0000000 2.0000000 3.0000000 2.0000000 0.0000000 3.0000000 3.0000000 3.0000000 0.0000000 4.0000000 3.0000000 4.0000000 0.0000000 5.0000000 3.0000000 5.0000000 0.0000000 6.0000000 3.0000000 6.0000000 0.0000000 7.00000...
result:
ok correct
Test #16:
score: 0
Accepted
time: 1ms
memory: 3848kb
input:
4 89 288.5915130114
output:
60 0.0000000 0.0000000 4.0000000 0.0000000 0.0000000 1.0000000 4.0000000 1.0000000 0.0000000 2.0000000 4.0000000 2.0000000 0.0000000 3.0000000 4.0000000 3.0000000 0.0000000 4.0000000 4.0000000 4.0000000 0.0000000 5.0000000 4.0000000 5.0000000 0.0000000 6.0000000 4.0000000 6.0000000 0.0000000 7.00000...
result:
ok correct
Test #17:
score: 0
Accepted
time: 1ms
memory: 3760kb
input:
95 3 175.9210001082
output:
4 0.0000000 0.0000000 67.7024451 0.0000000 27.2975549 3.0000000 95.0000000 3.0000000
result:
ok correct
Test #18:
score: 0
Accepted
time: 1ms
memory: 3756kb
input:
84 4 310.3037172015
output:
6 0.0000000 0.0000000 84.0000000 0.0000000 0.0000000 1.0000000 56.5358463 1.0000000 27.4641537 4.0000000 84.0000000 4.0000000
result:
ok correct
Test #19:
score: 0
Accepted
time: 1ms
memory: 3836kb
input:
2 2 2.8284271248
output:
4 0.0000000 0.0000000 0.0000000 0.0000000 2.0000000 2.0000000 2.0000000 2.0000000
result:
ok correct
Test #20:
score: 0
Accepted
time: 1ms
memory: 3652kb
input:
100 100 10000.0000000000
output:
102 0.0000000 0.0000000 100.0000000 0.0000000 0.0000000 1.0000000 100.0000000 1.0000000 0.0000000 2.0000000 100.0000000 2.0000000 0.0000000 3.0000000 100.0000000 3.0000000 0.0000000 4.0000000 100.0000000 4.0000000 0.0000000 5.0000000 100.0000000 5.0000000 0.0000000 6.0000000 100.0000000 6.0000000 0....
result:
ok correct
Test #21:
score: 0
Accepted
time: 1ms
memory: 3708kb
input:
100 100 9999.2500000000
output:
102 0.0000000 0.0000000 100.0000000 0.0000000 0.0000000 1.0000000 100.0000000 1.0000000 0.0000000 2.0000000 100.0000000 2.0000000 0.0000000 3.0000000 100.0000000 3.0000000 0.0000000 4.0000000 100.0000000 4.0000000 0.0000000 5.0000000 100.0000000 5.0000000 0.0000000 6.0000000 100.0000000 6.0000000 0....
result:
ok correct
Test #22:
score: 0
Accepted
time: 1ms
memory: 3664kb
input:
100 100 2723.8981892905
output:
28 0.0000000 0.0000000 100.0000000 0.0000000 0.0000000 1.0000000 100.0000000 1.0000000 0.0000000 2.0000000 100.0000000 2.0000000 0.0000000 3.0000000 100.0000000 3.0000000 0.0000000 4.0000000 100.0000000 4.0000000 0.0000000 5.0000000 100.0000000 5.0000000 0.0000000 6.0000000 100.0000000 6.0000000 0.0...
result:
ok correct
Test #23:
score: 0
Accepted
time: 1ms
memory: 3780kb
input:
100 100 8994.4904261819
output:
92 0.0000000 0.0000000 100.0000000 0.0000000 0.0000000 1.0000000 100.0000000 1.0000000 0.0000000 2.0000000 100.0000000 2.0000000 0.0000000 3.0000000 100.0000000 3.0000000 0.0000000 4.0000000 100.0000000 4.0000000 0.0000000 5.0000000 100.0000000 5.0000000 0.0000000 6.0000000 100.0000000 6.0000000 0.0...
result:
ok correct
Test #24:
score: 0
Accepted
time: 1ms
memory: 3844kb
input:
100 100 881.4998747190
output:
10 0.0000000 0.0000000 100.0000000 0.0000000 0.0000000 1.0000000 100.0000000 1.0000000 0.0000000 2.0000000 100.0000000 2.0000000 0.0000000 3.0000000 82.4100836 3.0000000 17.5899164 100.0000000 100.0000000 100.0000000
result:
ok correct
Test #25:
score: 0
Accepted
time: 1ms
memory: 3788kb
input:
88 94 8266.2500000000
output:
96 0.0000000 0.0000000 88.0000000 0.0000000 0.0000000 1.0000000 88.0000000 1.0000000 0.0000000 2.0000000 88.0000000 2.0000000 0.0000000 3.0000000 88.0000000 3.0000000 0.0000000 4.0000000 88.0000000 4.0000000 0.0000000 5.0000000 88.0000000 5.0000000 0.0000000 6.0000000 88.0000000 6.0000000 0.0000000 ...
result:
ok correct
Test #26:
score: 0
Accepted
time: 0ms
memory: 3660kb
input:
75 37 2772.0000000000
output:
38 0.0000000 0.0000000 75.0000000 0.0000000 0.0000000 1.0000000 75.0000000 1.0000000 0.0000000 2.0000000 75.0000000 2.0000000 0.0000000 3.0000000 75.0000000 3.0000000 0.0000000 4.0000000 75.0000000 4.0000000 0.0000000 5.0000000 75.0000000 5.0000000 0.0000000 6.0000000 75.0000000 6.0000000 0.0000000 ...
result:
ok correct
Test #27:
score: 0
Accepted
time: 1ms
memory: 3840kb
input:
48 39 62.0000000000
output:
4 0.0000000 0.0000000 0.3392857 0.0000000 47.6607143 39.0000000 48.0000000 39.0000000
result:
ok correct
Test #28:
score: 0
Accepted
time: 1ms
memory: 3724kb
input:
98 94 135.9000000000
output:
4 0.0000000 0.0000000 0.1900396 0.0000000 97.8099604 94.0000000 98.0000000 94.0000000
result:
ok correct
Test #29:
score: 0
Accepted
time: 0ms
memory: 3664kb
input:
90 81 7290.0000000000
output:
82 0.0000000 0.0000000 90.0000000 0.0000000 0.0000000 1.0000000 90.0000000 1.0000000 0.0000000 2.0000000 90.0000000 2.0000000 0.0000000 3.0000000 90.0000000 3.0000000 0.0000000 4.0000000 90.0000000 4.0000000 0.0000000 5.0000000 90.0000000 5.0000000 0.0000000 6.0000000 90.0000000 6.0000000 0.0000000 ...
result:
ok correct
Test #30:
score: 0
Accepted
time: 0ms
memory: 3700kb
input:
90 81 121.0826164250
output:
4 0.0000000 0.0000000 0.0000000 0.0000000 90.0000000 81.0000000 90.0000000 81.0000000
result:
ok correct
Test #31:
score: 0
Accepted
time: 1ms
memory: 3652kb
input:
34 99 3366.0000000000
output:
100 0.0000000 0.0000000 34.0000000 0.0000000 0.0000000 1.0000000 34.0000000 1.0000000 0.0000000 2.0000000 34.0000000 2.0000000 0.0000000 3.0000000 34.0000000 3.0000000 0.0000000 4.0000000 34.0000000 4.0000000 0.0000000 5.0000000 34.0000000 5.0000000 0.0000000 6.0000000 34.0000000 6.0000000 0.0000000...
result:
ok correct
Test #32:
score: 0
Accepted
time: 1ms
memory: 3648kb
input:
34 99 104.6756896330
output:
4 0.0000000 0.0000000 0.0000000 0.0000000 34.0000000 99.0000000 34.0000000 99.0000000
result:
ok correct
Test #33:
score: 0
Accepted
time: 0ms
memory: 3708kb
input:
3 3 5.9999
output:
4 0.0000000 0.0000000 1.4999500 0.0000000 1.5000500 3.0000000 3.0000000 3.0000000
result:
ok correct
Test #34:
score: 0
Accepted
time: 1ms
memory: 3836kb
input:
3 3 6.0
output:
4 0.0000000 0.0000000 1.5000000 0.0000000 1.5000000 3.0000000 3.0000000 3.0000000
result:
ok correct
Test #35:
score: 0
Accepted
time: 1ms
memory: 3704kb
input:
3 3 6.0001
output:
4 0.0000000 0.0000000 1.5000500 0.0000000 1.4999500 3.0000000 3.0000000 3.0000000
result:
ok correct
Test #36:
score: 0
Accepted
time: 1ms
memory: 3724kb
input:
4 4 13.999998
output:
6 0.0000000 0.0000000 4.0000000 0.0000000 0.0000000 1.0000000 1.2704330 1.0000000 2.7295670 4.0000000 4.0000000 4.0000000
result:
ok correct
Test #37:
score: 0
Accepted
time: 1ms
memory: 3836kb
input:
4 4 14.0
output:
6 0.0000000 0.0000000 4.0000000 0.0000000 0.0000000 1.0000000 1.2704348 1.0000000 2.7295652 4.0000000 4.0000000 4.0000000
result:
ok correct
Test #38:
score: 0
Accepted
time: 0ms
memory: 3784kb
input:
4 4 14.000002
output:
6 0.0000000 0.0000000 4.0000000 0.0000000 0.0000000 1.0000000 1.2704365 1.0000000 2.7295635 4.0000000 4.0000000 4.0000000
result:
ok correct
Test #39:
score: 0
Accepted
time: 1ms
memory: 3784kb
input:
4 4 15.123104
output:
6 0.0000000 0.0000000 4.0000000 0.0000000 0.0000000 1.0000000 1.9999992 1.0000000 2.0000008 4.0000000 4.0000000 4.0000000
result:
ok correct
Test #40:
score: 0
Accepted
time: 1ms
memory: 3840kb
input:
4 4 15.123106
output:
6 0.0000000 0.0000000 4.0000000 0.0000000 0.0000000 1.0000000 2.0000002 1.0000000 1.9999998 4.0000000 4.0000000 4.0000000
result:
ok correct
Test #41:
score: 0
Accepted
time: 0ms
memory: 3652kb
input:
4 4 15.123108
output:
6 0.0000000 0.0000000 4.0000000 0.0000000 0.0000000 1.0000000 2.0000012 1.0000000 1.9999988 4.0000000 4.0000000 4.0000000
result:
ok correct
Test #42:
score: 0
Accepted
time: 1ms
memory: 3708kb
input:
4 4 14.593385
output:
6 0.0000000 0.0000000 4.0000000 0.0000000 0.0000000 1.0000000 1.7067417 1.0000000 2.2932583 4.0000000 4.0000000 4.0000000
result:
ok correct
Test #43:
score: 0
Accepted
time: 1ms
memory: 3776kb
input:
4 4 14.593387
output:
6 0.0000000 0.0000000 4.0000000 0.0000000 0.0000000 1.0000000 1.7067429 1.0000000 2.2932571 4.0000000 4.0000000 4.0000000
result:
ok correct
Test #44:
score: 0
Accepted
time: 0ms
memory: 3660kb
input:
4 4 14.593389
output:
6 0.0000000 0.0000000 4.0000000 0.0000000 0.0000000 1.0000000 1.7067442 1.0000000 2.2932558 4.0000000 4.0000000 4.0000000
result:
ok correct
Test #45:
score: 0
Accepted
time: 0ms
memory: 3748kb
input:
2 2 4.0
output:
4 0.0000000 0.0000000 1.0000000 0.0000000 1.0000000 2.0000000 2.0000000 2.0000000
result:
ok correct
Test #46:
score: 0
Accepted
time: 1ms
memory: 3748kb
input:
3 3 5.0
output:
4 0.0000000 0.0000000 0.8750000 0.0000000 2.1250000 3.0000000 3.0000000 3.0000000
result:
ok correct
Test #47:
score: 0
Accepted
time: 1ms
memory: 3712kb
input:
4 4 15.123
output:
6 0.0000000 0.0000000 4.0000000 0.0000000 0.0000000 1.0000000 1.9999472 1.0000000 2.0000528 4.0000000 4.0000000 4.0000000
result:
ok correct
Test #48:
score: 0
Accepted
time: 1ms
memory: 3644kb
input:
4 4 14.1
output:
6 0.0000000 0.0000000 4.0000000 0.0000000 0.0000000 1.0000000 1.3560748 1.0000000 2.6439252 4.0000000 4.0000000 4.0000000
result:
ok correct
Test #49:
score: 0
Accepted
time: 1ms
memory: 3652kb
input:
3 3 9.0
output:
4 0.0000000 0.0000000 2.6250000 0.0000000 0.3750000 3.0000000 3.0000000 3.0000000
result:
ok correct
Test #50:
score: 0
Accepted
time: 1ms
memory: 3704kb
input:
4 4 16.0
output:
6 0.0000000 0.0000000 4.0000000 0.0000000 0.0000000 1.0000000 2.3888622 1.0000000 1.6111378 4.0000000 4.0000000 4.0000000
result:
ok correct