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