QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#165906#7110. Kuririn MIRACLEucup-team228AC ✓317ms3732kbC++202.2kb2023-09-05 22:52:392023-09-05 22:52:39

Judging History

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

  • [2023-09-05 22:52:39]
  • 评测
  • 测评结果:AC
  • 用时:317ms
  • 内存:3732kb
  • [2023-09-05 22:52:39]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()

typedef long long ll;
typedef pair<int, int> pii;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

template<typename T>
std::ostream& operator << (std::ostream& os, const vector<T>& a) {
    for (const T& x : a) {
        os << x << ' ';
    }
    return os;
}

typedef long double real_t;

const real_t eps = 1e-10;
const real_t pi = acos(-1.0);

real_t v, R;

real_t f(real_t x) {
    real_t sx = sin(x);
    return R / (v * (sqrt(3 + sx * sx) - sx));
}

real_t simpson(real_t l, real_t r) {
    return real_t(1) / real_t(6) * (r - l) * (f(l) + real_t(4) * f((l + r) / real_t(2)) + f(r));
}

real_t Integral(real_t l, real_t r) {
    real_t m  = (l + r) / real_t(2);
    real_t tot = simpson(l, r);
    real_t sum = simpson(l, m) + simpson(m, r);
    if (abs(tot - sum) < eps) return sum;
    return Integral(l, m) + Integral(m, r);
}

real_t T(real_t alpha) {
    return Integral(0, alpha);
}

bool check(real_t x1, real_t y1, real_t x2, real_t y2) {
    //cout << x1 << ' ' << y1 << ' ' << x2 << ' ' << y2 << '\n';
    return x1 * x2 + y1 * y2 < 0;
}

void solve() {
    real_t d;
    cin >> v >> R >> d;
    R *= 2;

    real_t time = (d - 2 * R) / v;

    if (d <= 2 * R || time < T(pi)) {
        cout << d / v << '\n';
        return;
    }

    real_t low = pi / 2, high = pi;
    real_t ans = 1000;

    while (high - low > eps) {
        real_t mid = (low + high) / 2;
        real_t a = mid;
        real_t t = T(a);
        real_t Xc = R + v * t;
        real_t Yc = 0;
        real_t X = Xc + R * cos(pi - a);
        real_t Y = Yc + R * sin(pi - a);
        real_t dist = sqrt(Y * Y + (X - d) * (X - d));
        if (check(d - dist / 2 - X, -Y, Xc - X, Yc - Y)) {
            high = mid;
            ans = min(ans, t + dist / (2 * v));
        } else {
            low = mid;
        }
    }

    cout << ans << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cout.precision(15);

    int t;
    cin >> t;
    while (t--) {
        solve();
    }

    return 0;
}


这程序好像有点Bug,我给组数据试试?

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

1
2.00 3 30.0

output:

8.3105799339928

result:

ok found '8.3105799', expected '8.3105799', error '0.0000000'

Test #2:

score: 0
Accepted
time: 30ms
memory: 3732kb

input:

100
8.66 6.05 71.59
8.44 8.67 82.55
4.23 9.68 24.74
6.63 9.95 7.45
1.2 7.27 97.55
2.08 2.94 31.61
8.48 5.56 20.16
7.35 5.55 52.48
1.35 8.15 51.23
3.88 9.02 72.37
7.03 1.97 57.03
1.78 4.44 93.44
5.5 6.11 52.94
1.09 9.64 69.01
1.01 3.54 16.78
1.63 4.55 44.06
5.82 5.51 5.92
5.62 2.93 76.01
4.75 4.43 73...

output:

4.45783712275524
5.48836080908331
5.84869976359338
1.1236802413273
43.2664800535558
8.30549013825902
2.37735849056604
4.01548596958401
37.9481481481481
18.6520618556701
4.15512364360147
27.1789630070998
9.62545454545455
63.3119266055046
16.6138613861386
15.0939944611827
1.01718213058419
6.9496235027...

result:

ok 100 numbers

Test #3:

score: 0
Accepted
time: 317ms
memory: 3608kb

input:

1000
7.52 6.68 80.67
5.34 6.82 45.75
3.57 6.35 22.35
9.55 3.65 31.38
9.37 5.73 40.42
1.83 8.38 82.97
4.86 6.13 9.45
3.88 5.34 84.19
6.49 4.15 85.24
6.51 7.23 42.97
3.0 5.98 57.53
9.35 2.76 69.07
6.76 9.16 91.24
2.98 9.89 49.2
9.16 3.85 66.14
1.84 3.03 37.43
8.01 5.04 50.98
4.05 9.86 4.76
5.4 5.49 60...

output:

5.77088264927324
8.56741573033708
6.26050420168067
3.28586387434555
4.31376734258271
25.1764841720827
1.94444444444444
11.406299616389
6.80719120566084
6.60061443932412
10.7277125608634
3.80019784485083
7.48448430271055
16.510067114094
3.77569701216
10.9157110704947
3.51752764608435
1.17530864197531...

result:

ok 1000 numbers

Extra Test:

score: 0
Extra Test Passed