QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#162311#7110. Kuririn MIRACLEucup-team266TL 42ms4456kbC++143.2kb2023-09-03 09:38:552023-09-03 09:38:56

Judging History

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

  • [2023-09-03 09:38:56]
  • 评测
  • 测评结果:TL
  • 用时:42ms
  • 内存:4456kb
  • [2023-09-03 09:38:55]
  • 提交

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-8);
	//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, 40){
			double mid = 0.5 * (lb + ub);
			double nt = calc(0, mid, 1e-8);
			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-8);
		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: 42ms
memory: 4456kb

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...

output:


result: