[清华集训2015]灯泡(浙江大学ZOJ 3203 Light Bulb)
Time Limit: 1 Second Memory Limit: 32768 KB
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 H, h 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
题目大意:
他的房子狭窄,他家里只有一个灯泡。每天晚上,他都在他不知名的房子里徘徊,想着如何赚更多的钱。有一天,他发现他的影子长度在灯泡和房子的墙壁之间行走时不时变化。突然想到了他的思绪,他想知道他的影子的最大长度。
输入的第一行包含整数T(T <= 100),表示个案数。
每个测试用例在一行中 包含三个实数H,h和D. H是灯泡的高度,而h是轻度高度的高度。 D是灯泡和墙壁之间的距离。所有数字的范围均为10 -2至10 3,包括两者,H - h > = 10 -2。
对于每个测试用例,在一行中输出mildleopard阴影的最大长度,精确到三位小数。
算法分析
参考:
https://blog.csdn.net/Mrx_Nh/article/details/52745348 分析理解应该是对的,但是代码有误,估计是没有讨论影子不落到墙上的情况。
https://blog.csdn.net/qq_38944163/article/details/80870928 代码是正确的。
这个题要分两种情况讨论:影子没有落到墙上;影子落到墙上。
影子没有落到墙上的情况如下图所示:
影子落到墙上的情况如下图所示
算影子的长度可以用相似三角形,相信各位上过初中的朋友都会。。
那么我们发现这是一个单峰函数,要求峰值,这里我们可以用一个很强大的东西,三分法。
具体看代码吧
#include<stdio.h>
double f(double x,double H,double h,double D)
{
double tanA,Y;
tanA=(H-h)/x;//这里大家可以画个图帮助理解
Y=H/tanA;//下面那条的长(在没有墙的情况下)
if(Y<=D) return Y-x;//如果没到墙,就直接返回地上影子的长度。
Y=Y-D;
return D-x+Y*tanA;//D-X是地上影子的长度,Y*tanA是墙上影子的长度.
}
int main()
{
freopen("p3382.in","r",stdin);
int i,T;
double H,h,D;
double L,R,m1,m2,fm1,fm2;
scanf("%d",&T);
for(i=;i<T;i++)
{
scanf("%lf%lf%lf",&H,&h,&D);
L=;R=D;
while(L+1e-<R)
{
m1=L+(R-L)/; m2=R-(R-L)/;
fm1=f(m1,H,h,D); fm2=f(m2,H,h,D);
if(fm1<fm2) L=m1;
else R=m2;
}
printf("%.3lf\n",f(L,H,h,D));
}
return ;
}
为何是一个单峰,可以考虑看一下第一个参考的博客。
理解时参考下图:
最新文章
- [LeetCode] Fraction to Recurring Decimal 分数转循环小数
- eclipse maven web环境搭建
- zepto源码--核心方法9(管理包装集)--学习笔记
- FancyTree 状态保持
- 曲线行驶s弯道技巧图解【转】
- JS 日历控件
- 加载网络映射盘中的assembly失败
- 【IT名人堂】何云飞:阿里云数据库的架构演进之路
- Strut2文件下载
- 学习linux能有什么用
- js函数大全(2)
- goroutine的意义与实现
- Linux环境下tomcat的安装与使用
- iOS ReplayKit实时录制屏幕实现方案的细节记录
- CSS中一个冒号和两个冒号有什么区别
- 深入学习 Java 序列化
- P3567 [POI2014]KUR-Couriers
- 2013级计算机学院数字媒体专业李成梁(笛卡尔积,概率树状图)&; 学生选课
- HDU1083(KB10-C 二分图最大匹配)
- Mutex, semaphore, spinlock
热门文章
- Mysql连接数过多、Mysql连接错误过多的问题处理
- php+js实现极验,拖动滑块验证码验证表单
- HTTP/2和Python的支持现状-2019-10
- python遍历列表删除多个元素的坑
- windows系统获取进程的pid号并终止
- c#时间与时间戳互转13位
- manager.add_command(&#39;runserver&#39;, Server(&#39;0.0.0.0&#39;, port=&#39;8093&#39;, extra_files=extra_files))
- List 分隔多次执行 且在同一个事物当中
- Win10 家庭版 VMware 无法启动 解决办法
- Android中使用ps命令查看进程PID