可以观察题目中隐含的单调性来解决本题。
观察到可以把图中的$L$分成两部分：一部分是投影到地上的，而另一部分是投影到墙上的。
位置离墙越近，地上的投影就会变短，同时墙上的投影也会变长。
但是本题的答案并不是一个一次函数，因为一开始墙上的投影一段时间内都为$0$（影子太短），所以并不能直接一次函数求解。
所以可以直接正常三分，函数直接快速维护一下即可。
复杂度约等于$\Theta(Tlogd)$ ? （不会证，算了…）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
| #pragma GCC optimize("O2")
#include <bits/stdc++.h>
#define PI 3.14159265
#define DO_NOT_USE_SCANF ios::sync_with_stdio(0)
#define PQ priority_queue
#define lowbit(x) ((x) & (-x))
#ifdef lmy
#define DEBUG printf("Passing [%s] in LINE %d...\n" , __FUNCTION__ , __LINE__)
#endif
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
inline void read(int &x) {
int f = 1;x = 0;char ch = getchar();
while(ch < '0' || ch > '9') {if(ch == '-') f = -1; ch = getchar();}
while(ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
x *= f;
}
inline void readll(ll &x) {
ll f = 1;x = 0;char ch = getchar();
while(ch < '0' || ch > '9') {if(ch == '-') f = -1; ch = getchar();}
while(ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
x *= f;
}
double H , h , D;
const double eps = 1e-7;
double f(double mid) {
double straight = mid / (H - h) * h;
if(straight + mid - D > eps) {
straight = D - mid;
}
double delta = H - h;
double up = h - delta * (straight / mid);
if(0 - up > eps) up = 0;
return straight + up;
}
void solve() {
scanf("%lf%lf%lf" , &H , &h , &D);
double l = 0 , r = D;
while(r - l > eps) {
double lmid = l + (r - l) / 3 , rmid = r - (r - l) / 3;
if(f(rmid) - f(lmid) > eps) l = lmid;
else r = rmid;
}
cout << fixed << setprecision(3) << f(l) << endl;
return;
}
int main(){
#ifdef lmy
int nol_cl = clock();
#endif
int T;
read(T);
while(T--) {
solve();
}
#ifdef lmy
printf("\nTime: %dms\n", int((clock() - nol_cl) / (double)CLOCKS_PER_SEC * 1000));
#endif
return 0;
}
|