开始上课!
首先我们需要理解题目。
题目的意思就是:两栋楼之间有两个楼梯,长度为x和y。已知两个楼梯交点离地面的高度,求两栋楼之间的距离。
首先我们可以利用算法标签中的“二分”。
(这里 盗 用一下 zpiceberg 的图))
下面我就来依着这张图讲解这道题。
首先我们得找出二分的方法。
在 yxc的讲解视频中,有这么一个思路:
两栋楼之间,架着长度为x的梯子的那栋楼,
可以看成一个以长度为x的梯子为斜边、
以a高的墙为一条直角边的直角三角形.
那么在这个三角形之间,
又有一个一条直角边为c的直角三角形
。另一边也同理
(另一边也可以构出一个以长度为y的梯子为斜边
、以b高的墙为一条直角边的直角三角形,与一个一条直角边为c的相似直角三角形)。
这两个三角形很容易看出是一组相似三角形。
因为相似三角形每条边的比值都是一样的,
然后我们再将下面以c为一条直角边的底边设为n
(另一边的以c为一条直角边的直角三角形的底边为m)
,那么就有:
a/c=n/s
b/c=s/m
又通过两条以c为一条直角边的直角三角形的底边
相加就是s(m+n=s),可以得到:
n=s*c/a
m=s*c/b
上面两个方程联立m+n=s这个方程后,可以得出:
(s*c/a)+(s*c/b)=s
两边同时除以s:
a/c+b/c=1
转化:
1/a+1/b=1/c
最后得出:c=a*b/(a+b)
得出最后推导算式后
,我们可以选择二分计算s来计算如果当前两栋
楼之间长度为s时,c应该是多少?
然后判断此时的c是大于给定的c,
还是小于给定的c,通过判断结果来调整
二分的双指针。
既然有了图文并茂,应该都会做了吧……
代码
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;
double x,y,c;
double calc(double s){
double a=sqrt(x*x-s*s);
double b=sqrt(y*y-s*s);
return a*b/(a+b);
}
int main(){
cin>>x>>y>>c;
double l=0,r=min(x,y);
while(r-l>1e-5){
double mid=(l+r)/2;
if(calc(mid)>c) l=mid;
else r=mid;
}
printf("%.3lf",r);
return 0;
}
Miss Yeung给小黄同学点个赞!!!