QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#162313 | #7110. Kuririn MIRACLE | ucup-team266 | TL | 32ms | 4404kb | C++14 | 3.2kb | 2023-09-03 09:39:38 | 2023-09-03 09:39:38 |
Judging History
answer
#include<bits/stdc++.h>
#define rep(i, n) for(int i = 0; i < n; ++i)
using namespace std;
typedef vector<int> vi;
typedef long long ll;
typedef pair<int, int> pii;
const int Mod = 1e9 + 7;
const int inv2 = (Mod+1) / 2;
const ll inf = 0x3f3f3f3f3f3f3f3fll;
inline int sign(int a){ return (a&1) ? (Mod-1) : 1; }
inline void uadd(int &a, int b){ a += b-Mod; a += (a>>31) & Mod; }
inline void usub(int &a, int b){ a -= b, a += (a>>31) & Mod; }
inline void umul(int &a, int b){ a = (int)(1ll * a * b % Mod); }
inline int add(int a, int b){ a += b-Mod; a += (a>>31) & Mod; return a; }
inline int sub(int a, int b){ a -= b, a += (a>>31) & Mod; return a; }
inline int mul(int a, int b){ a = (int)(1ll * a * b % Mod); return a; }
int qpow(int b, int p){ int ret = 1; while(p){ if(p&1) umul(ret, b); umul(b, b), p >>= 1; } return ret; }
int fact[200200], invfact[200200], pw2[200200], invpw2[200200];
void initfact(int n){
pw2[0] = 1; for(int i = 1; i <= n; ++i) pw2[i] = mul(pw2[i-1], 2);
invpw2[0] = 1; for(int i = 1; i <= n; ++i) invpw2[i] = mul(invpw2[i-1], (Mod+1) / 2);
fact[0] = 1; for(int i = 1; i <= n; ++i) fact[i] = mul(fact[i-1], i);
invfact[n] = qpow(fact[n], Mod-2); for(int i = n; i > 0; --i) invfact[i-1] = mul(invfact[i], i);
}
inline void chmax(int &a, int b){ (b>a) ? (a=b) : 0; }
double f(double x);
double simpson(double l, double r) {
double mid = (l + r) / 2;
return (r - l) * (f(l) + 4 * f(mid) + f(r)) / 6; // 辛普森公式
}
double asr(double l, double r, double eps, double ans, int step) {
double mid = (l + r) / 2;
double fl = simpson(l, mid), fr = simpson(mid, r);
if (abs(fl + fr - ans) <= 15 * eps && step < 0)
return fl + fr + (fl + fr - ans) / 15; // 足够相似的话就直接返回
return asr(l, mid, eps / 2, fl, step - 1) +
asr(mid, r, eps / 2, fr, step - 1); // 否则分割成两段递归求解
}
double calc(double l, double r, double eps) {
return asr(l, r, eps, simpson(l, r), 12);
}
double v, r, d;
const double pi = acos(-1);
inline double tan_v(double x){
double c = cos(x);
return v * (sqrt(c*c + 3) - c);
}
inline double f(double x){
return 1. / (tan_v(x) / (2.*r));
}
void solve(){
cin >> v >> r >> d;
double t = calc(0, 0.5 * pi, 1e-6);
//cout << t << endl;
if(2.*t*v + 4.*r < d + 1e-8){
double curans = t;
d -= 2.*r + t*v;
double lb = 0, ub = 0.5 * pi;
rep(cc, 30){
double mid = 0.5 * (lb + ub);
double nt = calc(0, mid, 1e-6);
double tv = tan_v(mid);
double a = acos((tv*tv + 4*v*v - v*v) / (2.*tv*2*v));
a = 0.5*pi - mid + a;
double nd = d - nt * v - 2*r * sin(mid);
double td = 2*r*cos(mid) * tan(a);
if(td > nd)
lb = mid;
else
ub = mid;
}
double mid = 0.5 * (lb + ub);
double nt = calc(0, mid, 1e-6);
double tv = tan_v(mid);
double a = acos((tv*tv + 4*v*v - v*v) / (2.*tv*2*v));
a = 0.5*pi - mid + a;
double nd = d - nt * v - 2*r * sin(mid);
double td = 2*r*cos(mid);
double x = sqrt(nd*nd + td*td);
cout << curans + nt + x / (2.*v) << "\n";
} else {
cout << d / v << "\n";
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout << fixed << setprecision(12);
int T;
cin >> T;
while(T--)
solve();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 32ms
memory: 4404kb
input:
1 2.00 3 30.0
output:
8.310579933906
result:
ok found '8.3105799', expected '8.3105799', error '0.0000000'
Test #2:
score: -100
Time Limit Exceeded
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...