《训练指南》——8.6

  修水管问题&＃xff1a;

  话说最近柴小俊迷上了一款战略经营游戏《部落冲突》&＃xff0c;他在修建筑的时候面临这样一个问题&＃xff0c;他的军营被夹在两条河流之间&＃xff0c;现在它想在两条河流的边上修筑供水点&＃xff0c;并且需要用水管将两个供水点分别与军营连接起来(两个供水点之间也要相连)&＃xff0c;那么身为Acmer的你&＃xff0c;能否当一次参谋&＃xff0c;告诉柴小俊他最少需要准备多长的水管呢&＃xff1f;

  输入&＃xff1a;我们以一条河流为x轴建系数&＃xff0c;两条河流在(0,0)交汇。

  点A的坐标(另一条河流上的一点,假定其在第一象限)。

  点B的坐标(数据保证它落在两条直线的内部)。

  输出&＃xff1a;

  输出柴小俊修建水管的最小长度。

 

  分析&＃xff1a;我们首先要做的应该是将这个实际问题抽象成数学(几何)问题&＃xff0c;很容易看到&＃xff0c;这道问题描述的是如下一个图形。

 

  

                       

  给出了直线OA&＃xff0c;和夹在x、OA之间的B&＃xff0c;那么现在需要你求解三角形BCD的最小周长&＃xff0c;其中C、D必须分别落在OA和x轴上。

  

  首先我们先进行最优解的分析&＃xff0c;也就是我们得找到这个最优三角形。我们任意画一个三角形BCD&＃xff0c;很容易看到&＃xff0c;这里我们分别做B关于OA、x轴的对称点&＃xff0c;记作E、F,那么根据中垂线的性质&＃xff0c;我们发现三角形的周长变成了DC&＃43;CD&＃43;DF&＃xff0c;那么为了使得和最小&＃xff0c;应该令E、C、D、F共线&＃xff0c;也就是说&＃xff0c;连接E、F,与OA、x的交点就是最优三角形的顶点C、D。

 

  那么现在问题的关键变成了怎么求一个点关于一条直线的对称点(点A关于直线l的对称点B)。

  容易看到&＃xff0c;我们可以把这个过程分为两个过程&＃xff1a;

(1)    作点关于A在直线l上的投影&＃xff0c;记作C。

(2)    基于投影&＃xff0c;我们进行向量运算&＃xff0c;点C &＃43; 向量CA。(想一想&＃xff0c;为什么)

 

那么我们的问题再次简化&＃xff1a;如何求A在l上的投影&＃xff1f;

这里就需要进行一些简单的运算。

 

  有了这些铺垫&＃xff0c;我们就不难求得两个对称点&＃xff0c;它们之间的距离也就是这道问题的最终解。