《训练指南》——8.6

  修水管问题:

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

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

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

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

  输出:

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

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

  

                       

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

  

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

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

  容易看到,我们可以把这个过程分为两个过程:

(1)    作点关于A在直线l上的投影,记作C。

(2)    基于投影,我们进行向量运算,点C + 向量CA。(想一想,为什么)

那么我们的问题再次简化:如何求A在l上的投影?

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

 

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

原文地址:https://www.cnblogs.com/rhythmic/p/5740798.html