本文共 2117 字，大约阅读时间需要 7 分钟。

计算几何(二分) - Crossed Ladders - UVA 10566

题意：

$如上图，给定三个浮点数x,y,c，计算两个房子之间的间距。$

$其中c是两条虚线交点的竖直高度。$

输入：

$多组测试数据，$

$每组包括三个浮点数。依次表示，x,y,c。$

输出：

$一个浮点数，表示答案。$

Sample Input

30 40 1012.619429 8.163332 310 10 310 10 1

Sample Output

26.0337.0008.0009.798

分析：

$建立如上图平面直角坐标系xOy$

$设两房之间的宽度为t，两条直线方程为y=k_{1}x和y=k_2(x-t)，t>0$

$其中k_1=\frac{\sqrt{y^2-t^2}}{t}，k_2=-\frac{\sqrt{x^2-t^2}}{t}$

$联立方程组\{\begin{array}{l}y=k_{1}x\\ y=k_2(x-t)\end{array}，得到交点(x_0,y_0)=(\frac{k_{2}t}{k_2-k_1},\frac{k_1{k}_{2}t}{k_2-k_1})，$

$则\frac{k_1{k}_{2}t}{k_2-k_1}=c。$

$若要强解方程，较为繁琐。$

$但容易证明，有唯一解满足题意。$

$当t较大时，交点的纵坐标会较小，反之会较大。$

$因此，我们可以二分t的值，确定y_1与y_2的交点，得到交点纵坐标后，$

$再检验与c的差，能够解一个满足误差范围的t。$

代码：

#include<cstring>#include<iostream>#include<cmath>#include<cstdio>#include<algorithm>using namespace std;const double eps=1e-5;double x,y,c;double cal(double t){       double k1=sqrt(y*y-t*t)/t, k2=-sqrt(x*x-t*t)/t;    return k1*k2*t/(k2-k1);}int main(){       while(~scanf("%lf%lf%lf",&x,&y,&c))    {            double l=0, r=min(x,y), t;        while(r-l>eps)        {               t=(l+r)/2;            if(cal(t)<c) r=t;            else l=t;        }        printf("%.3lf\n",t);    }    return 0;}