Light Bulb
Problem's Link: http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3203
Mean:
灯的位置固定，而人的位置不固定，求人的影子的最大长度。
analyse:
当灯、人的头部、右墙角在同一条直线上时，此时人的影子全部在地板上；当人继续往右走的时候，影子分为地板上的和墙上的，由此可见这是一个先增后减的凸函数，三分取最大值即可。
double cal(Type a) { return D-x+H-(H-h)*D/x; }
推导过程如下：（运用2次相似三角形）
1>k/(D+k) = z/H; ---> k = Dz/(H-z)
2>k/(y+k) = z/h; ---> k = zy/(h-z)
So D/(H-z) = y/(h-z) ----解出z----> z = H - (H-h)*D/x
L = z + y ---> L = D-x+H-(H-h)*D/x;
Time complexity: O(n)
Source code:
// Memory Time // 1347K 0MS // by : crazyacking // 2015-03-31-21.36 #include<map> #include<queue> #include<stack> #include<cmath> #include<cstdio> #include<vector> #include<string> #include<cstdlib> #include<cstring> #include<climits> #include<iostream> #include<algorithm> #define MAXN 1000010 #define LL long long using namespace std; double D, H, h; double cal(double x) { return D-x+H-(H-h)*D/x; } int main() { int T; scanf("%d", &T); while(T--) { scanf("%lf%lf%lf", &H, &h, &D); double left=(H-h)*D/H, right=D, mid, midmid; while(left+1e-9<=right) { mid=(left+right)/2; midmid=(mid+right)/2; if(cal(mid)>=cal(midmid)) right=midmid; else left=mid; } printf("%.3lf\n", cal(mid)); } return 0; }
