QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#251039#854. Archer Vladthomas_li#AC ✓719ms3644kbC++172.4kb2023-11-14 06:16:182023-11-14 06:16:19

Judging History

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

  • [2023-11-14 06:16:19]
  • 评测
  • 测评结果:AC
  • 用时:719ms
  • 内存:3644kb
  • [2023-11-14 06:16:18]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int ll
#define rep(i,a,b) for(int i = a; i < (b); i++)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define PB push_back
#define FS first
#define SD second
#define cmx(x,y) x = max(x,y)
#define cmn(x,y) x = min(x,y)
#define ary(k) array<int,k>
typedef pair<int,int> pii;
typedef vector<int> vi;

const int g = 10;

long double geth(long double v, long double tan, long double x) {
    long double vx = sqrtl((long double)(v*v) / (1 + tan*tan));
    long double vy = sqrtl(v*v-vx*vx);
    long double t = x / vx;
    long double h = vy * t - g * t*t/2;
    return h;
}

long double ternary(int x, int v) {
    long double pocz = 0, kon = 1e9;
    while (kon - pocz > 1e-4) {
        long double tan1 = (2*pocz + kon) / 3, tan2 = (pocz+2*kon)/3;
        long double h1 = geth(v, tan1, x), h2 = geth(v, tan2, x);
        if (h1 > h2) {
            kon = tan2;
        } else {
            pocz = tan1;
        }
    }
    return (pocz + kon) / 2;
}

long double bs(int x, int y, int v, bool left, long double peakx) {
    long double pocz = 0, kon = 1e9;
    if (left)
        kon = peakx;
    else
        pocz = peakx;
    while (kon - pocz > 1e-4) {
        long double tan = (pocz + kon) / 2;
        long double vx = sqrtl((long double)(v*v) / (1 + tan*tan));
        long double vy = sqrtl(v*v-vx*vx);
        long double t = x / vx;
        long double h = vy * t - g * t*t/2;
//        cerr << tan << " " << vx << " " << t << " " << h << "\n";
        bool collide = (h <= y + 1e-6);
        if (collide && left)
            pocz = tan;
        else if (collide)
            kon = tan;
        else if (left)
            kon = tan;
        else
            pocz = tan;
    }
    return (pocz + kon) / 2;
}

void fun() {
    int c, n;
    cin >> c >> n;
    long double low = 0, high = 1e9;
    for (int i = 0; i < n; i++) {
        int x, y;
        cin >> x >> y;
        long double mid = ternary(x, c);
//        cerr << mid << " " << bs(x, y, c, true, mid) << " " << bs(x, y, c, false, mid) << "\n";
        low = max(low, bs(x, y, c, true, mid));
        high = min(high, bs(x, y, c, false, mid));
    }
    cout << fixed << setprecision(3) << (low+high)/2 << "\n";
}

signed main(){
	cin.tie(0)->sync_with_stdio(0); cin.exceptions(cin.failbit);
    int z;
    cin >> z;
    while (z--) fun();
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3644kb

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: 712ms
memory: 3572kb

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: 676ms
memory: 3636kb

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: 719ms
memory: 3588kb

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!