C# · 12月 19, 2021

C计算影子的最大长度

题面

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

思路

首先,分治肯定是能够想到的,但是是二分还是三分呢,我们只需要思考一下就能知道,我们设地上影长为L1,墙上为L2,人走近时L1增加,L2减小,走远时L1减小,L2增加——这是个二次函数,所以一定使用三分法。

然后让我们来算L的长度,首先L1=D-X(X为人到左墙距离),L2=H-(H-h)*D/X(相似三角形)。

如果不理解可看下图 ,两个蓝的三角形为相似三角形,对应边的比值相同。

然后三分一下x的范围即可。

@H_419_40@

代码

1 (我都讲得这么详细了还需要代码?)

2 #include

3 using namespace std;

4 double H,h,D,mid1,mid2;

5 int t;

6 double check(double x)

7 {

8 return D-x+H-(H-h)*D/x;

9 }

10 int main()

11 {

12 cin>>t;

13 while (t–)

14 {

15 cin>>H>>h>>D;

16 double l=(H-h)*D/H,r=D;//注意l要从(H-h)*D/H开始,不然墙上没有影子。

17 while (l+1e-10<=r)

18 {

19 mid1=(l+r)/2;

20 mid2=(mid1+r)/2;

21 if (check(mid1)>=check(mid2)) r=mid2;else l=mid1;

22 }

23 printf(“%.3lfn”,check(mid1));

24 }

25 return 0;

26 }