QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#346007 | #3195. Within Arm's Reach | PetroTarnavskyi# | AC ✓ | 1ms | 4040kb | C++20 | 2.8kb | 2024-03-07 19:33:27 | 2024-03-07 19:33:30 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define RFOR(i, a, b) for(int i = (a) - 1; i >= (b); i--)
#define SZ(a) int(a.size())
#define ALL(a) a.begin(), a.end()
#define PB push_back
#define MP make_pair
#define F first
#define S second
typedef long long LL;
typedef vector<int> VI;
typedef pair<int, int> PII;
typedef long double db;
const db EPS = 1e-9;
struct Pt
{
db x, y;
Pt operator+(const Pt& p) const
{
return {x + p.x, y + p.y};
}
Pt operator-(const Pt& p) const
{
return {x - p.x, y - p.y};
}
Pt operator*(db d) const
{
return {x * d, y * d};
}
Pt operator/(db d) const
{
return {x / d, y / d};
}
};
db sq(const Pt& p)
{
return p.x * p.x + p.y * p.y;
}
db abs(const Pt& p)
{
return sqrt(sq(p));
}
int sgn(db x)
{
return (EPS < x) - (x < -EPS);
}
Pt perp(const Pt& p)
{
return {-p.y, p.x};
}
vector<Pt> circleCircle(const Pt& o1, db r1,
const Pt& o2, db r2)
{
Pt d = o2 - o1;
db d2 = sq(d);
if (sgn(d2) == 0)
{
assert(sgn(r2 - r1) != 0);
return {};
}
db pd = (d2 + r1 * r1 - r2 * r2) / 2;
db h2 = r1 * r1 - pd * pd / d2;
if (sgn(h2) == -1)
return {};
Pt p = o1 + d * pd / d2;
if (sgn(h2) == 0)
return {p};
Pt h = perp(d) * sqrt(h2 / d2);
return {p - h, p + h};
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout << fixed << setprecision(15);
int n;
cin >> n;
VI l(n), sufSum(n), sufMx(n), rMin(n);
for (int& li : l)
cin >> li;
Pt target;
cin >> target.x >> target.y;
sufSum[n - 1] = l[n - 1];
sufMx[n - 1] = l[n - 1];
RFOR(i, n - 1, 0)
{
sufSum[i] = sufSum[i + 1] + l[i];
sufMx[i] = max(sufMx[i + 1], l[i]);
}
FOR(i, 0, n)
{
rMin[i] = max(0, 2 * sufMx[i] - sufSum[i]);
}
db absTarget = abs(target);
if (sgn(absTarget - rMin[0]) < 0)
{
if (sgn(absTarget) == 0)
target = {(db)rMin[0], 0};
else
target = target * (rMin[0] / absTarget);
}
else if (sgn(absTarget - sufSum[0]) > 0)
target = target * (sufSum[0] / absTarget);
Pt p = {0, 0};
vector<Pt> ans;
FOR(i, 0, n - 1)
{
Pt q = {p.x + l[i], p.y};
db dist = abs(target - q);
// rMin[i + 1] <= dist && dist <= sufSum[i + 1]
if (sgn(rMin[i + 1] - dist) <= 0 && sgn(dist - sufSum[i + 1]) <= 0)
{
p = q;
}
else
{
vector<Pt> vec;
vec = circleCircle(p, l[i], target, sufSum[i + 1]);
if (!vec.empty())
p = vec[0];
else
{
assert(rMin[i + 1] != 0);
vec = circleCircle(p, l[i], target, rMin[i + 1]);
assert(!vec.empty());
p = vec[0];
}
}
ans.PB(p);
}
ans.PB(target);
for (const Pt& q : ans)
cout << q.x << " " << q.y << "\n";
assert(sgn(abs(ans[0]) - l[0]) == 0);
FOR(i, 0, n - 1)
assert(sgn(abs(ans[i + 1] - ans[i]) - l[i + 1]) == 0);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3928kb
input:
2 4 2 -8 -3
output:
-3.745316710276178 -1.404493766353567 -5.617975065414267 -2.106740649530350
result:
ok ACCEPTED
Test #2:
score: 0
Accepted
time: 1ms
memory: 4040kb
input:
1 10 10 0
output:
10.000000000000000 0.000000000000000
result:
ok ACCEPTED
Test #3:
score: 0
Accepted
time: 1ms
memory: 3872kb
input:
1 10 0 0
output:
10.000000000000000 0.000000000000000
result:
ok ACCEPTED
Test #4:
score: 0
Accepted
time: 0ms
memory: 3964kb
input:
2 10 5 2 2
output:
7.071067811865475 7.071067811865475 3.535533905932738 3.535533905932738
result:
ok ACCEPTED
Test #5:
score: 0
Accepted
time: 0ms
memory: 3756kb
input:
3 100 20 20 80 90
output:
86.311321218928029 50.501047805397308 83.155660609464014 70.250523902698654 80.000000000000000 90.000000000000000
result:
ok ACCEPTED
Test #6:
score: 0
Accepted
time: 0ms
memory: 3872kb
input:
3 5 10 4 5 3
output:
4.055075586697438 -2.925125977829063 5.629949608868375 6.950083985219375 5.000000000000000 3.000000000000000
result:
ok ACCEPTED
Test #7:
score: 0
Accepted
time: 0ms
memory: 3804kb
input:
3 3 3 3 -1 -1
output:
3.000000000000000 0.000000000000000 0.471405860129076 1.614376559483697 -1.000000000000000 -1.000000000000000
result:
ok ACCEPTED
Test #8:
score: 0
Accepted
time: 0ms
memory: 3816kb
input:
11 31 1 62 125 250 500 2 7 3 1000 15 -2 -3
output:
17.195706082982103 25.793559124473154 17.750406279207332 26.625609418810998 52.141818445171537 78.212727667757306 121.479342973325178 182.219014459987767 260.154392029632458 390.231588044448687 537.504490142247019 806.256735213370529 538.613890534697478 807.920835802046216 542.496791908274081 813.74...
result:
ok ACCEPTED
Test #9:
score: 0
Accepted
time: 0ms
memory: 3868kb
input:
3 5 3 4 5 3
output:
5.000000000000000 0.000000000000000 7.981423969999720 0.333333333333333 5.000000000000000 3.000000000000000
result:
ok ACCEPTED
Test #10:
score: 0
Accepted
time: 1ms
memory: 3868kb
input:
20 3 9 15 5 7 13 4 17 8 999 16 6 10 14 2 12 1000 11 998 1 234 -123
output:
3.000000000000000 0.000000000000000 12.000000000000000 0.000000000000000 27.000000000000000 0.000000000000000 32.000000000000000 0.000000000000000 39.000000000000000 0.000000000000000 52.000000000000000 0.000000000000000 56.000000000000000 0.000000000000000 73.000000000000000 0.000000000000000 81.00...
result:
ok ACCEPTED
Test #11:
score: 0
Accepted
time: 0ms
memory: 3816kb
input:
20 11 857 509 877 13 811 991 997 937 853 787 739 919 7 859 941 929 773 947 863 9871 -7919
output:
11.000000000000000 0.000000000000000 868.000000000000000 0.000000000000000 1377.000000000000000 0.000000000000000 2254.000000000000000 0.000000000000000 2267.000000000000000 0.000000000000000 3078.000000000000000 0.000000000000000 4069.000000000000000 0.000000000000000 5066.000000000000000 0.0000000...
result:
ok ACCEPTED
Test #12:
score: 0
Accepted
time: 0ms
memory: 3852kb
input:
20 919 625 820 609 760 41 101 232 545 812 234 177 678 131 359 444 519 77 173 917 0 0
output:
919.000000000000000 0.000000000000000 1544.000000000000000 0.000000000000000 2364.000000000000000 0.000000000000000 2973.000000000000000 0.000000000000000 3733.000000000000000 0.000000000000000 3774.000000000000000 0.000000000000000 3875.000000000000000 0.000000000000000 4107.000000000000000 0.00000...
result:
ok ACCEPTED
Test #13:
score: 0
Accepted
time: 0ms
memory: 3808kb
input:
20 919 625 820 609 760 41 101 232 545 812 234 177 678 131 359 444 519 77 173 917 0 -20000
output:
0.000000000000000 -919.000000000000000 0.000000000000000 -1544.000000000000000 0.000000000000000 -2364.000000000000000 0.000000000000000 -2973.000000000000000 0.000000000000000 -3733.000000000000000 0.000000000000000 -3774.000000000000000 0.000000000000000 -3875.000000000000000 0.000000000000000 -41...
result:
ok ACCEPTED
Test #14:
score: 0
Accepted
time: 0ms
memory: 3932kb
input:
20 408 663 148 685 731 606 538 289 850 577 732 34 656 200 325 901 105 575 754 910 -2498 1075
output:
408.000000000000000 0.000000000000000 1071.000000000000000 0.000000000000000 1219.000000000000000 0.000000000000000 1904.000000000000000 0.000000000000000 2635.000000000000000 0.000000000000000 3241.000000000000000 0.000000000000000 3779.000000000000000 0.000000000000000 4049.180270340308621 102.584...
result:
ok ACCEPTED
Test #15:
score: 0
Accepted
time: 0ms
memory: 3736kb
input:
20 440 377 296 985 425 377 777 533 710 620 975 854 312 130 13 900 745 416 550 507 -1080 -2184
output:
440.000000000000000 0.000000000000000 817.000000000000000 0.000000000000000 1113.000000000000000 0.000000000000000 2098.000000000000000 0.000000000000000 2523.000000000000000 0.000000000000000 2900.000000000000000 0.000000000000000 3677.000000000000000 0.000000000000000 4210.000000000000000 0.000000...
result:
ok ACCEPTED
Test #16:
score: 0
Accepted
time: 1ms
memory: 3864kb
input:
4 890 306 65 120 -10 14
output:
-517.301992409995799 724.222789373994119 -339.443105131952300 475.220347184733220 -301.662622540211033 422.327671556295447 -231.914039293919465 324.679655011487251
result:
ok ACCEPTED
Test #17:
score: 0
Accepted
time: 1ms
memory: 3960kb
input:
20 149 380 248 401 43 631 977 207 511 496 14 425 179 867 9 801 432 766 684 358 -3887 7982
output:
-65.234837156882222 133.960501720152790 -231.605562791883862 475.604734295039101 -340.184352153674405 698.572549238649114 -515.749249468505083 1059.097120982147562 -534.575410527202637 1097.756863089305750 -810.838378621113255 1665.066101917603807 -1238.586270582683260 2543.451405143035189 -1329.214...
result:
ok ACCEPTED
Test #18:
score: 0
Accepted
time: 0ms
memory: 3808kb
input:
20 121 803 712 959 971 452 892 694 465 489 201 20 757 995 643 853 797 755 203 452 2501 643
output:
121.000000000000000 0.000000000000000 924.000000000000000 0.000000000000000 1636.000000000000000 0.000000000000000 2595.000000000000000 0.000000000000000 3566.000000000000000 0.000000000000000 4018.000000000000000 0.000000000000000 4910.000000000000000 0.000000000000000 5604.000000000000000 0.000000...
result:
ok ACCEPTED
Test #19:
score: 0
Accepted
time: 0ms
memory: 3748kb
input:
20 397 740 397 939 260 942 166 856 939 700 98 740 470 621 506 843 433 261 951 662 10019 -4091
output:
397.000000000000000 0.000000000000000 1137.000000000000000 0.000000000000000 1534.000000000000000 0.000000000000000 2473.000000000000000 0.000000000000000 2733.000000000000000 0.000000000000000 3675.000000000000000 0.000000000000000 3841.000000000000000 0.000000000000000 4697.000000000000000 0.00000...
result:
ok ACCEPTED
Test #20:
score: 0
Accepted
time: 0ms
memory: 3868kb
input:
6 870 915 808 598 10 881 -4251 -946
output:
-849.226298514601961 -188.983316489017515 -1742.378095228235058 -387.741632106777315 -2531.084818446394120 -563.257172018416570 -3114.805883402407882 -693.156049329258494 -3124.567105224414801 -695.328271357867890 -3984.530747743224373 -886.701032078355741
result:
ok ACCEPTED
Test #21:
score: 0
Accepted
time: 0ms
memory: 3812kb
input:
1 500 -40 80
output:
-223.606797749978970 447.213595499957939
result:
ok ACCEPTED