QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#162314 | #7110. Kuririn MIRACLE | ucup-team266 | TL | 32ms | 4032kb | C++14 | 3.2kb | 2023-09-03 09:40:27 | 2023-09-03 09:40:28 |
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-1);
//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-1);
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-1);
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;
}
详细
Test #1:
score: 100
Accepted
time: 32ms
memory: 4032kb
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...