QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#163073#7110. Kuririn MIRACLEhos_lyricAC ✓37ms3952kbC++172.9kb2023-09-03 20:02:272023-09-03 20:02:27

Judging History

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

  • [2023-09-03 20:02:27]
  • 评测
  • 测评结果:AC
  • 用时:37ms
  • 内存:3952kb
  • [2023-09-03 20:02:27]
  • 提交

answer

#include <cassert>
#include <cmath>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

using namespace std;

using Int = long long;

template <class T1, class T2> ostream &operator<<(ostream &os, const pair<T1, T2> &a) { return os << "(" << a.first << ", " << a.second << ")"; };
template <class T> ostream &operator<<(ostream &os, const vector<T> &as) { const int sz = as.size(); os << "["; for (int i = 0; i < sz; ++i) { if (i >= 256) { os << ", ..."; break; } if (i > 0) { os << ", "; } os << as[i]; } return os << "]"; }
template <class T> void pv(T a, T b) { for (T i = a; i != b; ++i) cerr << *i << " "; cerr << endl; }
template <class T> bool chmin(T &t, const T &f) { if (t > f) { t = f; return true; } return false; }
template <class T> bool chmax(T &t, const T &f) { if (t < f) { t = f; return true; } return false; }
#define COLOR(s) ("\x1b[" s "m")


using Double = double;
constexpr Double PI = acos(-1.0L);

/*
  x = V t + 2R (1 - cos(q))
  y = 2R sin(q)
  
  dx/dt = V + 2R sin(q) dq/dt
  dy/dt = 2R cos(q) dq/dt
  
  (2V)^2
  = (dx/dt)^2 + (dy/dt)^2
  = V^2 + 4R V sin(q) dq/dt + 4R^2 (dq/dt)^2
  
  dq/dt
  = (-2R V sin(q) + sqrt(4R^2 V^2 sin(q)^2 + 12R^2 V^2)) / (4R^2)
  = (V/2R) (-sin(q) + sqrt(sin(q)^2 + 3))
  
  dt (V/2R)
  = dq / (-sin(q) + sqrt(sin(q)^2 + 3))
  = dq (sin(q) + sqrt(sin(q)^2 + 3)) / 3
  
  \int[q] dq sin(q)
  = 1 - cos(q)
  
  \int[q] dq sqrt(sin(q)^2 + 3)
  = \int[q] dq sqrt(4 - cos(q)^2)
  = \int[q] dq 2 sqrt(1 - (1/2)^2 sin(q+PI/2)^2)
*/

Double V, R, D;

Double ans;
bool check(Double q) {
  Double t = 0.0;
  t += (1.0 - cos(q));
  t += 2.0 * (ellint_2(0.5, q + PI/2) - ellint_2(0.5, PI/2));
// cerr<<q<<": "<<t<<endl;
  t /= 3.0;
  t /= (V / (2*R));
  Double dx = D - (V * t + 2*R * (1.0 - cos(q)));
  Double dy = 0.0 - (2*R * sin(q));
  const Double e = sqrt(dx*dx + dy*dy);
  (dx /= e) *= (2*V);
  (dy /= e) *= (2*V);
  dx -= V;
  // above tangent? (sin(q), cos(q))
  if (sin(q) * dy >= cos(q) * dx) {
    chmin(ans, t + e / (2*V));
    return true;
  } else {
    return false;
  }
}

int main() {
  for (int numCases; ~scanf("%d", &numCases); ) { for (int caseId = 1; caseId <= numCases; ++caseId) {
    scanf("%lf%lf%lf", &V, &R, &D);
    
    ans = D / V;
    Double lo = PI/2, hi = PI;
    if (check(hi)) {
      for (int iter = 0; iter < 100; ++iter) {
        const Double mid = (lo + hi) / 2.0;
        (check(mid) ? hi : lo) = mid;
      }
    }
    printf("%.12f\n", ans);
  }
#ifndef LOCAL
  break;
#endif
  }
  return 0;
}

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

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

1
2.00 3 30.0

output:

8.310579933906

result:

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

Test #2:

score: 0
Accepted
time: 5ms
memory: 3924kb

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.457837122737
5.488360808997
5.848699763593
1.123680241327
43.266480053535
8.305490138204
2.377358490566
4.015485969512
37.948148148148
18.652061855670
4.155123643576
27.178963007081
9.625454545455
63.311926605505
16.613861386139
15.093994461159
1.017182130584
6.949623502734
8.150430299228
8.858447...

result:

ok 100 numbers

Test #3:

score: 0
Accepted
time: 37ms
memory: 3900kb

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.770882649252
8.567415730337
6.260504201681
3.285863874346
4.313767342583
25.176484172057
1.944444444444
11.406299616371
6.807191205657
6.600614439324
10.727712560829
3.800197844820
7.484484302630
16.510067114094
3.775697012155
10.915711070456
3.517527646048
1.175308641975
6.095287438928
14.4431818...

result:

ok 1000 numbers

Extra Test:

score: 0
Extra Test Passed