A. Light Bulb

Time Limit: 1000ms
Case Time Limit: 1000ms
Memory Limit: 32768KB
 
64-bit integer IO format: %lld      Java class name: Main
 

Compared to wildleopard's wealthiness, his brother mildleopard is rather poor. His house is narrow and he has only one light bulb in his house. Every night, he is wandering in his incommodious house, thinking of how to earn more money. One day, he found that the length of his shadow was changing from time to time while walking between the light bulb and the wall of his house. A sudden thought ran through his mind and he wanted to know the maximum length of his shadow.

Input

The first line of the input contains an integer T (T <= 100), indicating the number of cases.

Each test case contains three real numbers Hh and D in one line. H is the height of the light bulb while h is the height of mildleopard. D is distance between the light bulb and the wall. All numbers are in range from 10-2 to 103, both inclusive, and H -h >= 10-2.

Output

For each test case, output the maximum length of mildleopard's shadow in one line, accurate up to three decimal places..

Sample Input

3
2 1 0.5
2 0.5 3
4 3 4

Sample Output

1.000
0.750
4.000 解题:好吧,比较喜欢数学解法,速度快嘛。。。参阅某神的代码。。。

算法:利用函数的凸性

 
 

思路一:

 
 
 L = 0 时,倾斜角越小 shadow 越长
所以 L 正好为 0 时,  X 的长度为左极限 
 
(H-h)/ X = H / D 
 
所以 X =  (H-h)*D / H ,left = X = (H-h)*D / H
 
明显可以看到右边的极限就是 X = D , 从而 right = D
 
也就是如果用所谓的三分法 X 的取值区间是 【left, right】
 
下面再分析假设 X 已经知道了,如何求出 shadow = D-X+L
 
 
L / H = ? / (D + ?) ..........................................(1)
 
tan(a) = L / ? = (H-h) / X  可以得到 ? = L *X / (H-h) 带入 (1)
 
可以得到 L = H - D*(H-h)/ X
 
所以 shadow = D - X + L = D+H - 【X+ (H-h)*D / X】
 
要使得 shadow 最大 , 则 【】中的函数值最小
 
注意到 【】中的值由  X 确定 ,而 前面我们已经确定了 X 的区间,
 
容易看出 【】中的函数是个单峰函数:
 
 
根据 a^2 + b^2 >= 2ab 成立的条件是 a = b
所以我们可以确定如果 X = (H-h)*D / X 求出的值就是上图中的 X0
 
那么要使得【】中的值最小,结果是显然的了。既然能确定极值点,那么也没有必要用三分了
 
分下面三种情况即可求出满足条件的 X 使得shadow 最大 :
 
(1) X 的取值范围覆盖了 X0: X = X0
(2) X 的取值范围所在的区间单调递减【right <= X0】: X = right
(3) X 的取值范围所在的区间单调递增【left >= X0】: X = left
 
把所求的 X 带入上面的shadow 公式就是答案了。
 
想到根据函数的极值求主要是想的是三分图中的 X 本来就比较复杂了,虽然弄到这一步三分和求极值都一样。
但是如果真的用三分的思路的话, 还是觉得荆红浅醉 童鞋的三分 L 比较好,
虽然无法轻易的求出极值点,但是至少可以一眼看出 L 的取值范围是【0, H】话说要是所有的三分都能求出极值点,那么也 就失去了三分的意义了。
 

学妹的思路:三分 L

 
令所求 shadow =  S + L
PS : S 就是上图的 D - X
 
由 L / H = ? / (D+?)      可以得到  ?= (L*D)  /  (H-L)
 
而 L / h = ? / (S+ ?)      可得 S = ?* (h-L) / L   =  D*(h-L) / (H-L)   前面又已经确定了 L 的范围【0, H】
 
shadow = S + L 随便乱搞都可以三分出来了。

 #include<stdio.h>
#include<string.h>
#include<math.h> int main()
{
int T;
double H,h,D;
scanf("%d", &T);
while(T--)
{
scanf("%lf%lf%lf", &H,&h,&D);
double x1 = (H-h)*D/H;
double x2 = D;
double x0 = sqrt(D*(H-h)); double x; if(x1 <= x0 && x0 <= x2) x = x0;
else if(x0 <= x1) x = x1;
else if(x0 >= x2) x = x2; double ans = D+H- (x + (H-h)*D/x);
printf("%.3lf\n", ans);
}
return ;
}

最新文章

  1. Python 爬取网站资源文件
  2. VS Extract Method
  3. ORACLE &quot;ORA--22992:无法使用远程表选择的LOB定位器,database link&quot;
  4. WPF socket通讯 UDP接收消息
  5. android上传图片至服务器
  6. [Regex Expression] Confirmative -- World bundry
  7. 【Android基础】Activity之间进行参数传递的三种方式
  8. Linux之特殊权限(SUID/SGID/SBIT)
  9. VC++6.0在win8.1系统下运行失败的解决办法
  10. Python——爬虫——数据提取
  11. 爬虫框架 Scrapy
  12. 利用微信支付的订单查询接口可以在APP 中提高支付的可靠性
  13. PostgreSQL在Update时使用Substring函数截取字符串并且加上CASE WHEN THEN条件判断
  14. C# wkhtmltopdf 将html转pdf(详解)
  15. hdu 5826 physics 物理题
  16. c# 递归函数使用案例
  17. 你曾后悔进入 IT 行业吗?为什么?(转自知乎)--一生不悔入IT
  18. Yii2在Form中处理短信验证码的Validator,耦合度最低的短信验证码验证方式
  19. 搜狐 WEB 标准-前端技术应用规范
  20. nxlog以syslog方式发送日志

热门文章

  1. office 导出问题
  2. 涉及到弹出层的opacity样式问题
  3. Android Studio中通过CMake使用NDK并编译自定义库和添加预编译库
  4. 最小化安装centos后ifconfig看不到eth0
  5. selenium的定位
  6. HDU 1950 Bridging signals (LIS,O(nlogn))
  7. spark简单入门
  8. AEE加密解密
  9. Linux文件操作函数
  10. Python基础篇 -- 运算符和编码