判断是否相交

首先进行快速排斥实验，也就是判断两根线段在 xx 轴与 yy 轴是否都有公共区域。显然，如果它们在 xx 轴或者 yy 轴都没有公共点那么它们显然不可能相交。但是，即使通过了测试，那么也不一定相交。

接着进行跨立实验，即判断一根线段的端点是否分别在另外一根线段的两侧。如果对于两个线段都满足，那么这两根线段就是相交。要判断一个点在一根线段的那一侧只需要将这跟线段与终点与这个点组成的线段进行叉乘即可。如果叉乘结果小于 00 那么点在线段左侧，如果叉乘结果等于 00 那么点在线段上，对于其他情况点在线段右侧。

求解交点

首先使用判断线段是否有交点的方式将没有交点的情况和重合的情况特判掉，接着开始求解交点。为了便于书写，首先求解出 d→=st→−ed→\overrightarrow{d}=\overrightarrow{st}-\overrightarrow{ed}。

设 S1E→=λd1\overrightarrow{S_1E}=\lambda d_1，连接 S1,S2S_1,S_2 得到上图。

观察一下两个式子：

S1S2→×d2=∣S1S2∣⋅∣d2∣⋅sin⁡∠S1S2E\overrightarrow{S_1S_2}\times d_2=|S_1S_2|\cdot |d_2|\cdot \sin \angle S_1S_2E

d1×d2=∣d1∣⋅∣d2∣⋅sin⁡∠S1ES2d_1\times d_2=|d_1|\cdot |d_2|\cdot\sin\angle S_1ES_2

坐商得到：

S1S2→×d2d1×d2=∣S1S2∣⋅sin⁡∠S1S2E∣d1∣⋅sin⁡∠S1ES2=∣S1E∣∣d1∣=∣λ∣\dfrac{\overrightarrow{S_1S_2}\times d_2}{d_1\times d_2}=\dfrac{|S_1S_2|\cdot \sin\angle S_1S_2E}{|d_1|\cdot \sin\angle S_1ES_2}=\dfrac{|S_1E|}{|d_1|}=|\lambda|

事实上，直接将绝对值去掉就可以了（但是我不会证明），于是得到：

E=S1+d1⋅S1S2→×d2d1×d2E=S_1+d_1\cdot \dfrac{\overrightarrow{S_1S_2}\times d_2}{d_1\times d_2}

求解最短距离

如果两个线段相交，那么显然它们之间的距离为 00。

接下来考虑如果两个线段，因为特判了相交的情况而且线段都是直的，所以肯定距离最短的两点的连线的其中一个位置必然在一根线段的端点。所以可以范围内四种情况，一次讨论四个端点，在最后取一个最小值就好了。

过线段的两个端点做垂线，如果这个点被夹在连根直线之内，那么直接做高距离最短。对于在两根直线之外的点，那么肯定是与线段中的其中一个端点连接最短。

成品