QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#346072#3195. Within Arm's ReachKhNURE_KIVI#AC ✓1ms4036kbC++203.0kb2024-03-07 20:09:122024-03-07 20:09:16

Judging History

你现在查看的是最新测评结果

  • [2024-03-07 20:09:16]
  • 评测
  • 测评结果:AC
  • 用时:1ms
  • 内存:4036kb
  • [2024-03-07 20:09:12]
  • 提交

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';
    }
}

Details

Tip: Click on the bar to expand more detailed information

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