QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#163269#7110. Kuririn MIRACLEPhantomThresholdTL 303ms3972kbC++201.5kb2023-09-03 23:09:212023-09-03 23:09:22

Judging History

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

  • [2023-09-03 23:09:22]
  • 评测
  • 测评结果:TL
  • 用时:303ms
  • 内存:3972kb
  • [2023-09-03 23:09:21]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

typedef long double db;
const db eps=1e-10;
const db pi=acos(-1);
int sign(db k){
	if (k<-eps) return -1;
	else if (k>eps) return 1;
	return 0;	
}
int cmp(db k1,db k2){return sign(k1-k2);}

db f(db theta){
	db s=sin(theta);
	return (sqrtl(s*s+3)+s)/3;
}

double simpson(double l, double r) {
    return (f(l) + 4 * f((l + r) / 2) + f(r)) * (r - l) / 6;
}
double Integral(double l, double r, double eps, double st) {
    double mid = (l + r) / 2;
    double sl = simpson(l, mid);
    double sr = simpson(mid, r);
    if (std::abs(sl + sr - st) <= 15 * eps)
        return sl + sr + (sl + sr - st) / 15;
    return Integral(l, mid, eps / 2, sl) + Integral(mid, r, eps / 2, sr);
}
double Integral(double l, double r) {
    return Integral(l, r, eps, simpson(l, r));
}

db solve(db v,db r,db d){
	r=r*2;
	d/=v;
	r/=v;
	v=1;
	auto check=[&](db t){
		db x=d-v*t-r;
		db theta=acos(r/x);
		db t1=Integral(0,pi-theta)*r/v;
		db t2=hypot(x-r*cos(theta),r*sin(theta))*f(theta)/v;
		return t1+t2<=t;
	};
	db ans=d/v;
	db L=0,R=(d-2*r)/v-eps;
	if (R<L) return ans;
	for (int cc=1;cc<=100;cc++){
		db mid=(L+R)/2;
		if (check(mid)) R=mid;
		else L=mid;
	}
	if (check(R)) ans=min(ans,R);
	return ans;
}

int main(){
	ios_base::sync_with_stdio(false);
	int T;
	cin >> T;
	for (;T--;){
		db v,r,d;
		cin >> v >> r >> d;
		cout << fixed << setprecision(12) << solve(v,r,d) << "\n";
	}
	return 0;	
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 5ms
memory: 3972kb

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: 303ms
memory: 3904kb

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: -100
Time Limit Exceeded

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: