ZOJ3203灯泡

  • Z时代
  • 2024-01-10
  • 分类：综合

coding

题面

  相比 wildleopard 的家，他的弟弟 mildleopard 比较穷。他的房子是狭窄的而且在他的房间里面仅有一个灯泡。每天晚上，他徘徊在自己狭小的房子里，思考如何赚更多的钱。有一天，他发现他的影子的长度随着他在灯泡和墙壁之间走到时发生着变化。一个突然的想法出现在脑海里，他想知道他的影子的最大长度。 

思路

首先，分治肯定是能够想到的，但是是二分还是三分呢，我们只需要思考一下就能知道，我们设地上影长为L1，墙上为L2，人走近时L1增加，L2减小，走远时L1减小，L2增加——这是个二次函数，所以一定使用三分法。 
然后让我们来算L的长度，首先L1=D-X（X为人到左墙距离），L2=H-(H-h)*D/X(相似三角形)。 
如果不理解可看下图 ，两个蓝的三角形为相似三角形，对应边的比值相同。 
然后三分一下x的范围即可。

代码

 1（我都讲得这么详细了还需要代码？)
 2 #include<bits/stdc++.h>
 3usingnamespace std;
 4double H,h,D,mid1,mid2;
 5int t; 
 6double check(double x)
 7{
 8return D-x+H-(H-h)*D/x;
 9}
10int main()
11{
12     cin>>t;
13while (t--)
14    {
15         cin>>H>>h>>D;
16double l=(H-h)*D/H,r=D;//注意l要从（H-h）*D/H开始，不然墙上没有影子。
17while (l+1e-10<=r)
18        {
19             mid1=(l+r)/2;
20             mid2=(mid1+r)/2;
21if (check(mid1)>=check(mid2)) r=mid2;else l=mid1;  
22        }
23         printf("%.3lf\n",check(mid1));
24    }
25return0;
26  }

以上是 ZOJ3203灯泡 的全部内容， 来源链接： utcz.com/z/509189.html

回到顶部