QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#163073 | #7110. Kuririn MIRACLE | hos_lyric | AC ✓ | 37ms | 3952kb | C++17 | 2.9kb | 2023-09-03 20:02:27 | 2023-09-03 20:02:27 |
Judging History
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