QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#54316#854. Archer Vladckiseki#AC ✓991ms3936kbC++2.2kb2022-10-07 20:26:522022-10-07 20:26:53

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-10-07 20:26:53]
  • 评测
  • 测评结果:AC
  • 用时:991ms
  • 内存:3936kb
  • [2022-10-07 20:26:52]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

const int maxc = 1000025;

const int g = 10;

using llf = long double;
const llf PI = acos(-1);

pair<llf,llf> SO(llf C, llf X, llf Y) {
    const auto f = [&](llf TAN) {
        // llf t = X / vx;
        // llf vy = sqrt(max<llf>(0, C*C-vx*vx));
        // return t * vy - 0.5 * g * t * t;
        const llf SEC2 = TAN*TAN+1;
        return X * TAN - 0.5 * g * X * X * SEC2 / C / C;
    };

    llf l = 0, r = 1e9;
    for (int iter = 0; iter < 100; iter++) {
        llf m1 = (l * 2 + r) / 3;
        llf m2 = (l + r * 2) / 3;
        if (f(m1) < f(m2)) {
            l = m1;
        } else {
            r = m2;
        }
    }
    llf mx = (l+r)/2;
    l = 0, r = mx;
    for (int iter = 0; iter < 100; iter++) {
        llf m = (l + r) / 2;
        if (f(m) <= Y) {
            l = m;
        } else {
            r = m;
        }
    }
    llf L = (l+r)/2;
    l = mx, r = 1e9;
    for (int iter = 0; iter < 100; iter++) {
        llf m = (l + r) / 2;
        if (f(m) <= Y) {
            r = m;
        } else {
            l = m;
        }
    }
    llf R = (l+r)/2;
    // cerr << "Y = " << Y << endl;
    // cerr << f((0+L)/2) << ' ';
    // cerr << f(L) << ' ' << f((L+R)/2) << ' ';
    // cerr << f(R) << ' ';
    // cerr << f((R+C)/2) << ' ' << f(C) << ' ';
    // cerr << endl;
    return { L, R };
}

signed main() {
    cin.tie(nullptr) -> sync_with_stdio(false);
    int T;
    cin >> T;
    while (T--) {
        int C;
        cin >> C;
        int N;
        cin >> N;
        vector<pair<llf,int>> seg;
        llf mx = -1e9;
        llf mn = 1e9;
        for (int i = 0; i < N; i++) {
            int x, y;
            cin >> x >> y;
            auto [l, r] = SO(C, x, y);
            mx = max(mx, l);
            mn = min(mn, r);
            // seg.emplace_back(l, -1);
            // seg.emplace_back(r, 1);
            // cerr << l << ',' << r << endl;
        }
        // const auto gettan = [&C](llf vx) {
        //     llf vy = sqrt(max<llf>(0, C*C-vx*vx));
        //     return vy / vx;
        // };
        assert (mx <= mn);
        cout << fixed << setprecision(3);
        cout << (mx+mn)/2 << '\n';
        // sort(seg.begin(), seg.end());
    }
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 2ms
memory: 3724kb

input:

3
5
1
1 1
5
1
1 1
13
1
7 7

output:

2.500
2.500
2.414

result:

ok OK!

Test #2:

score: 0
Accepted
time: 991ms
memory: 3868kb

input:

15000
793
16
5023 26074
2250 212
5095 26384
7864 30618
2655 18285
8220 30295
8967 14062
1385 10550
2123 483
5949 29841
1133 4219
2799 9397
14596 297
9182 26752
7963 19230
9743 27315
823
20
1236 29918
2106 33247
2170 32933
233 7895
3534 6371
3689 1660
406 2521
2844 24587
3493 8197
1027 25571
3508 598...

output:

8.442
36.185
20.572
273.910
18.696
29.060
110.278
12.082
14.515
13.183
19.789
215.756
83.673
10.710
113.555
15.339
97.488
5.116
101.252
99.085
15.614
152.796
444.002
60.898
44.910
25.631
823.818
34.669
6.492
317.574
29.716
195.074
37.203
13.910
21.407
1543.894
281.493
33.724
3.837
11.687
47.155
15.6...

result:

ok OK!

Test #3:

score: 0
Accepted
time: 960ms
memory: 3936kb

input:

3
19112
96700
61 1139
1404681 996391
611808 8078391
300933 11496043
153415 6845133
1042621 1458903
543181 10794457
540016 8901506
605856 17717943
601862 17736824
550847 13224828
589935 4906022
1004257 15398146
196961 8477541
1240948 7039907
323244 12250962
1073473 13597516
780105 9198741
1323591 570...

output:

50.443
24.470
135.487

result:

ok OK!

Test #4:

score: 0
Accepted
time: 966ms
memory: 3724kb

input:

300
2226986
999
433999235 186709993
848826471 261170474
799455940 83848717
993614583 969953940
898743613 36130940
748035930 519926360
721067416 477366656
719083956 425975922
28336416 604459608
52425916 861079714
571083926 496364771
155240245 648550377
215332457 745715814
761358368 780244098
95625137...

output:

813.916
636.209
3041.703
2773.208
500.477
1071.019
1062.261
1148.308
558.132
586.469
204.772
951.174
3308.495
1137.213
504.847
369.550
5507.769
267.721
3222.394
182.591
4955.533
1061.095
1806.549
339.700
673.189
2300.869
578.931
275.501
592.149
3319.903
1326.553
296.076
1615.773
737.142
940.851
323....

result:

ok OK!