QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#423464#7110. Kuririn MIRACLEucup-team3215TL 180ms3944kbC++201.7kb2024-05-28 03:11:192024-05-28 03:11:19

Judging History

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

  • [2024-05-28 03:11:19]
  • 评测
  • 测评结果:TL
  • 用时:180ms
  • 内存:3944kb
  • [2024-05-28 03:11:19]
  • 提交

answer

#include <array>
#include <cmath>
#include <iostream>

using namespace std;

double midpoint(double r, double d, double mt, double h, auto& deriv) {
  double x = 0, y = 0, t = 0, c = 1;
  auto mp = [&] {
    auto [dx, dy] = deriv(x, y, t);
    return deriv(x + dx * h * c / 2, y + dy * h * c / 2, t + h * c / 2);
  };
  while (1) {
    // cout << t << ' ' << x << ' ' << y << ' ' << (x - t - 2 * r) * (x - t - 2 * r) + y * y - 4 * r * r << '\n';
    if (t >= mt) return 1. / 0;
    if (c < 1e-9) return t + sqrt((x - d) * (x - d) + y * y) / 2;
    auto [dx, dy] = mp();
    auto nx = x + dx * h * c, ny = y + dy * h * c, nt = t + h * c;
    auto [ndx, ndy] = deriv(nx, ny, nt);
    if (ndy < 0 && nx - ny / ndy * ndx < d) { c /= 2; continue; }
    x = nx, y = ny, t = nt;
    double coef = sqrt(((x - t - 2 * r) * (x - t - 2 * r) + y * y) / (4 * r * r));
    if (abs(coef - 1) > 1e-12) {
      x = (t + 2 * r) + (x - t - 2 * r) / coef;
      y = y / coef;
    }
  }
}

int main() {
  cin.tie(0)->sync_with_stdio(0);
  for (int tc = (cin >> tc, tc); tc--; ) {
    double v, r, d; cin >> v >> r >> d;
    auto deriv = [&](double x, double y, double t) -> array<double, 2> {
      double dx = x - t - 2 * r;
      if (abs(dx) < y) {
        double r = -dx / y, rr = r * r;
        double ux = (rr + sqrt(3 * rr + 4)) / (1 + rr);
        return {ux, (ux - 1) * r};
      } else {
        double r = -y / dx, rr = r * r, d = sqrt(4 * rr + 3);
        double uy = (-r + (dx < 0? d: -d)) / (1 + rr);
        return {uy * r + 1, uy};
      }
    };
    cout.precision(20);
    double ans = d;
    if (d >= 7 * r) ans = min(ans, midpoint(r, d, d - 4 * r, (d - 4 * r) / 1e5, deriv));
    cout << ans / v << '\n';
  }
}

详细

Test #1:

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

input:

1
2.00 3 30.0

output:

8.3105799339287909078

result:

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

Test #2:

score: 0
Accepted
time: 180ms
memory: 3944kb

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.4578371227435038548
5.4883608090111035693
5.8486997635933795081
1.1236802413273001555
43.266480053670335337
8.3054901382142016786
2.3773584905660376521
4.0154859695248257268
37.948148148148142411
18.652061855670105217
4.1551236436370544425
27.178963007303014621
9.6254545454545450411
63.31192660550...

result:

ok 100 numbers

Test #3:

score: -100
Time Limit Exceeded

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.7708826492619200721
8.5674157303370783723
6.2605042016806731198
3.2858638743455492737
4.3137673425827109952
25.176484172091178948
1.9444444444444441977
11.406299616421632592
6.8071912057100565363
6.6006144393241168444
10.727712560837838751
3.800197844864176222
7.4844843026435814437
16.510067114093...

result: