QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#346072 | #3195. Within Arm's Reach | KhNURE_KIVI# | AC ✓ | 1ms | 4036kb | C++20 | 3.0kb | 2024-03-07 20:09:12 | 2024-03-07 20:09:16 |
Judging History
answer
//#pragma GCC optimize("Ofast", "unroll-loops")
//#pragma GCC target("sse", "sse2", "sse3", "ssse3", "sse4")
#include <bits/stdc++.h>
#define all(a) a.begin(),a.end()
#define len(a) (int)(a.size())
#define mp make_pair
#define pb push_back
#define fir first
#define sec second
#define fi first
#define se second
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
typedef long double ld;
template<typename T>
bool umin(T &a, T b) {
if (b < a) {
a = b;
return true;
}
return false;
}
template<typename T>
bool umax(T &a, T b) {
if (a < b) {
a = b;
return true;
}
return false;
}
#ifdef KIVI
#define DEBUG for (bool _FLAG = true; _FLAG; _FLAG = false)
#define LOG(...) print(#__VA_ARGS__" ::", __VA_ARGS__) << endl
template <class ...Ts> auto &print(Ts ...ts) { return ((cerr << ts << " "), ...); }
#else
#define DEBUG while (false)
#define LOG(...)
#endif
const int max_n = -1, inf = 1000111222;
const ld PI = acos(-1.0);
inline ld sqr (ld x) {
return x * x;
}
inline ld dist (ld x0, ld y0, ld x1, ld y1) {
return sqrtl(sqr(x0 - x1) + sqr(y0 - y1));
}
int main() {
// freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
ios_base::sync_with_stdio(0);
cin.tie(0);
int n;
cin >> n;
vector <pii> a(n);
for (int i = 0; i < n; i++) {
cin >> a[i].first;
a[i].second = i;
}
sort(all(a));
reverse(all(a));
ld x, y;
cin >> x >> y;
ld X = 0, Y = 0;
cout << fixed;
cout.precision(10);
auto f = [&] (int pos, ld angle) -> ld {
ld tox = X + a[pos - 1].first * cos(angle);
ld toy = Y + a[pos - 1].first * sin(angle);
if (pos == n) {
return dist(x, y, tox, toy);
}
ld L = a[pos].first, R = a[pos].first;
for (int i = pos + 1; i < n; i++) {
R += a[i].first;
L -= a[i].first;
}
umax(L, ld(0));
ld cur_x = x - tox;
ld cur_y = y - toy;
ld d = dist(cur_x, cur_y, 0, 0);
if (d >= L && d <= R) {
return 0;
}
if (d < L) {
return L - d;
}
return d - R;
};
vector <pair<ld, ld> > ans(n);
for (int i = 0; i < n; i++) {
ld l = 0, r = 2 * PI;
for (int it = 0; it < 60; it++) {
ld m1 = l + (r - l) / 3;
ld m2 = r - (r - l) / 3;
if (f(i + 1, m1) < f(i + 1, m2)) {
r = m2;
}
else {
l = m1;
}
}
ld angle = (l + r) / 2.0;
ans[a[i].second].first = a[i].first * cos(angle);
ans[a[i].second].second = a[i].first * sin(angle);
X += ans[a[i].second].first;
Y += ans[a[i].second].second;
}
X = 0;
Y = 0;
for (auto &i : ans) {
X += i.first;
Y += i.second;
cout << X << ' ' << Y << '\n';
}
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3892kb
input:
2 4 2 -8 -3
output:
-3.7453167102 -1.4044937666 -5.6179750654 -2.1067406497
result:
ok ACCEPTED
Test #2:
score: 0
Accepted
time: 0ms
memory: 3864kb
input:
1 10 10 0
output:
10.0000000000 0.0000000009
result:
ok ACCEPTED
Test #3:
score: 0
Accepted
time: 0ms
memory: 3916kb
input:
1 10 0 0
output:
8.0724648165 -5.9021446768
result:
ok ACCEPTED
Test #4:
score: 0
Accepted
time: 0ms
memory: 3808kb
input:
2 10 5 2 2
output:
7.0710678116 7.0710678121 3.5355339062 3.5355339057
result:
ok ACCEPTED
Test #5:
score: 0
Accepted
time: 0ms
memory: 3820kb
input:
3 100 20 20 80 90
output:
40.0335063728 91.6368832267 60.0167669203 90.8187769437 80.0000000000 89.9999999992
result:
ok ACCEPTED
Test #6:
score: 0
Accepted
time: 0ms
memory: 3804kb
input:
3 5 10 4 5 3
output:
3.1588359060 -3.8757909798 2.4729651050 6.1006603554 5.0000000000 3.0000000000
result:
ok ACCEPTED
Test #7:
score: 0
Accepted
time: 0ms
memory: 3916kb
input:
3 3 3 3 -1 -1
output:
-2.5285941398 1.6143765596 -4.0000000002 -0.9999999998 -1.0000000002 -1.0000000000
result:
ok ACCEPTED
Test #8:
score: 0
Accepted
time: 0ms
memory: 3756kb
input:
11 31 1 62 125 250 500 2 7 3 1000 15 -2 -3
output:
17.1957060272 25.7935591617 17.7504062222 26.6256094568 52.1418182667 78.2127277868 121.4793425439 182.2190147462 260.1543910985 390.2315886652 537.5044880284 806.2567366226 538.6138884180 807.9208372132 542.4967897812 813.7451892805 544.1608903655 816.2413401664 -10.5393037006 -15.8089556109 -2.218...
result:
ok ACCEPTED
Test #9:
score: 0
Accepted
time: 0ms
memory: 3892kb
input:
3 5 3 4 5 3
output:
-1.7990717556 4.6651195931 1.1148222320 3.9515217869 5.0000000000 3.0000000000
result:
ok ACCEPTED
Test #10:
score: 0
Accepted
time: 1ms
memory: 3812kb
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:
0.2567521475 2.9889928629 1.0270085830 11.9559714524 2.3107692995 26.9009357689 2.7386895451 31.8825905405 3.3377778845 38.8569072212 4.4503705071 51.8092096287 4.7927067030 55.7945334460 6.2476341820 72.7321597859 6.9323065721 80.7028074207 -686.7427453462 799.6019118479 -685.3734006343 815.5432071...
result:
ok ACCEPTED
Test #11:
score: 0
Accepted
time: 1ms
memory: 3764kb
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:
5.1183481186 -9.7366581812 403.8841985072 -768.3108447732 640.7241252207 -1218.8525732672 1048.7960899880 -1995.1297605985 1054.8450468577 -2006.6367202660 1432.2068956152 -2724.4939728603 2423.2068956152 -2724.4939729450 3420.2068956152 -2724.4939730302 4357.2068956152 -2724.4939731103 4754.1115283...
result:
ok ACCEPTED
Test #12:
score: 0
Accepted
time: 1ms
memory: 3820kb
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.0000000000 -0.0000000785 301.9351561282 99.2772805928 1121.9351561282 99.2772805228 520.6683566217 196.0204240068 1280.6683566217 196.0204239419 1240.1889828845 202.5335109093 1140.4715012304 218.5779446034 911.4174839355 255.4324851795 373.3380034373 342.0088830414 1185.3380034373 342.008882972...
result:
ok ACCEPTED
Test #13:
score: 0
Accepted
time: 1ms
memory: 3812kb
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.0000012387 -919.0000000000 0.0000008448 -1544.0000000000 0.0000020202 -2364.0000000000 0.0000020315 -2973.0000000000 0.0000028469 -3733.0000000000 0.0000028477 -3774.0000000000 0.0000028495 -3875.0000000000 0.0000030985 -4107.0000000000 0.0000038011 -4652.0000000000 0.0000049650 -5464.0000000000 0...
result:
ok ACCEPTED
Test #14:
score: 0
Accepted
time: 1ms
memory: 3756kb
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:
-394.2468733334 105.0400060304 -1034.8980428905 275.7300143644 -1177.9091635939 313.8327617085 -1839.8187480692 490.1866728634 -2546.1795423244 678.3765459683 -3131.7521042114 834.3918489521 -3651.6168538423 972.9004843910 -3930.8750557893 1047.3038219863 -3080.8750557893 1047.3038219137 -3638.42516...
result:
ok ACCEPTED
Test #15:
score: 0
Accepted
time: 1ms
memory: 3956kb
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:
-425.7446451106 -111.0922911801 -790.5303979528 -206.2781857411 -1076.9404320063 -281.0129995393 -91.9404320063 -281.0129996234 -503.1710551927 -388.3180533429 -867.9568080267 -483.5039479350 -90.9568080267 -483.5039480014 -606.6883894739 -618.0771098800 -1293.6839170626 -797.3454703711 -1893.596821...
result:
ok ACCEPTED
Test #16:
score: 0
Accepted
time: 0ms
memory: 3956kb
input:
4 890 306 65 120 -10 14
output:
-517.3019926710 724.2227891876 -339.4431052847 475.2203470757 -301.6626226403 422.3276714848 -231.9140393364 324.6796549812
result:
ok ACCEPTED
Test #17:
score: 0
Accepted
time: 1ms
memory: 3856kb
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.2348369995 133.9605017968 -231.6055623902 475.6047344907 -340.1843514770 698.5725495682 -515.7492484950 1059.0971214562 -534.5754095083 1097.7568635855 -810.8383777038 1665.0661023643 -1238.5862706458 2543.4514051123 -1329.2145341603 2729.5576055795 -1552.9393782488 3188.9791920745 -1770.0969568...
result:
ok ACCEPTED
Test #18:
score: 0
Accepted
time: 1ms
memory: 3804kb
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:
-115.3585690834 36.5157574074 687.6414309166 36.5157573388 8.8354351431 251.3794818291 967.8354351431 251.3794817472 1938.8354351431 251.3794816642 1507.9092100203 387.7854511137 2399.9092100203 387.7854510375 1738.2658396293 597.2229128669 1294.9457186124 737.5520627312 828.7445590615 885.124007332...
result:
ok ACCEPTED
Test #19:
score: 0
Accepted
time: 1ms
memory: 3824kb
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:
247.3650648531 -310.5149347297 958.9994829951 -513.4347585906 1206.3645479900 -823.9496932074 2145.3645479900 -823.9496932876 2307.3668573272 -1027.3096002738 3249.3668573272 -1027.3096003542 3352.7991009529 -1157.1470794524 4208.7991009529 -1157.1470795255 5147.7991009529 -1157.1470796057 5583.9651...
result:
ok ACCEPTED
Test #20:
score: 0
Accepted
time: 0ms
memory: 4020kb
input:
6 870 915 808 598 10 881 -4251 -946
output:
-849.2262985491 -188.9833163339 -1742.3780951805 -387.7416323215 -2531.0848184307 -563.2571720891 -3114.8058834298 -693.1560492060 -3124.5671052499 -695.3282712435 -3984.5307476963 -886.7010322891
result:
ok ACCEPTED
Test #21:
score: 0
Accepted
time: 0ms
memory: 4036kb
input:
1 500 -40 80
output:
-223.6067979332 447.2135954084
result:
ok ACCEPTED