QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#162314#7110. Kuririn MIRACLEucup-team266TL 32ms4032kbC++143.2kb2023-09-03 09:40:272023-09-03 09:40:28

Judging History

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

  • [2023-09-03 09:40:28]
  • 评测
  • 测评结果:TL
  • 用时:32ms
  • 内存:4032kb
  • [2023-09-03 09:40:27]
  • 提交

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

output:


result: