计算几何(二分) - Crossed Ladders - UVA 10566
计算几何(二分) - Crossed Ladders - UVA 10566
题意:
如
上
图
,
给
定
三
个
浮
点
数
x
,
y
,
c
,
计
算
两
个
房
子
之
间
的
间
距
。
如上图,给定三个浮点数x,y,c,计算两个房子之间的间距。
如上图,给定三个浮点数x,y,c,计算两个房子之间的间距。
其 中 c 是 两 条 虚 线 交 点 的 竖 直 高 度 。 其中c是两条虚线交点的竖直高度。 其中c是两条虚线交点的竖直高度。
输入:
多 组 测 试 数 据 , 多组测试数据, 多组测试数据,
每 组 包 括 三 个 浮 点 数 。 依 次 表 示 , x , y , c 。 每组包括三个浮点数。依次表示,x,y,c。 每组包括三个浮点数。依次表示,x,y,c。
输出:
一 个 浮 点 数 , 表 示 答 案 。 一个浮点数,表示答案。 一个浮点数,表示答案。
Sample Input
30 40 10
12.619429 8.163332 3
10 10 3
10 10 1
Sample Output
26.033
7.000
8.000
9.798
分析:
建
立
如
上
图
平
面
直
角
坐
标
系
x
O
y
建立如上图平面直角坐标系xOy
建立如上图平面直角坐标系xOy
设 两 房 之 间 的 宽 度 为 t , 两 条 直 线 方 程 为 y = k 1 x 和 y = k 2 ( x − t ) , t > 0 设两房之间的宽度为t,两条直线方程为y=k_1x和y=k_2(x-t),t>0 设两房之间的宽度为t,两条直线方程为y=k1x和y=k2(x−t),t>0
其 中 k 1 = y 2 − t 2 t , k 2 = − x 2 − t 2 t 其中k_1=\frac{\sqrt{y^2-t^2}}{t},k_2=-\frac{\sqrt{x^2-t^2}}{t} 其中k1=ty2−t2 ,k2=−tx2−t2
联 立 方 程 组 { y = k 1 x y = k 2 ( x − t ) , 得 到 交 点 ( x 0 , y 0 ) = ( k 2 t k 2 − k 1 , k 1 k 2 t k 2 − k 1 ) , 联立方程组\begin{cases}y=k_1x\\y=k_2(x-t)\end{cases},得到交点(x_0,y_0)=(\frac{k_2t}{k_2-k_1},\frac{k_1k_2t}{k_2-k_1}), 联立方程组{y=k1xy=k2(x−t),得到交点(x0,y0)=(k2−k1k2t,k2−k1k1k2t),
则 k 1 k 2 t k 2 − k 1 = c 。 则\frac{k_1k_2t}{k_2-k_1}=c。 则k2−k1k1k2t=c。
若 要 强 解 方 程 , 较 为 繁 琐 。 若要强解方程,较为繁琐。 若要强解方程,较为繁琐。
但 容 易 证 明 , 有 唯 一 解 满 足 题 意 。 但容易证明,有唯一解满足题意。 但容易证明,有唯一解满足题意。
当 t 较 大 时 , 交 点 的 纵 坐 标 会 较 小 , 反 之 会 较 大 。 当t较大时,交点的纵坐标会较小,反之会较大。 当t较大时,交点的纵坐标会较小,反之会较大。
因 此 , 我 们 可 以 二 分 t 的 值 , 确 定 y 1 与 y 2 的 交 点 , 得 到 交 点 纵 坐 标 后 , 因此,我们可以二分t的值,确定y_1与y_2的交点,得到交点纵坐标后, 因此,我们可以二分t的值,确定y1与y2的交点,得到交点纵坐标后,
再 检 验 与 c 的 差 , 能 够 解 一 个 满 足 误 差 范 围 的 t 。 再检验与c的差,能够解一个满足误差范围的t。 再检验与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;
}