优化线段上的2参数距离函数（ACM ICPC Regionals Elim。）

这个问题是ACM ICPC坎普尔地区消除回合中提出的问题的子问题： 给定2个线段，分别由2D点

(Pa, Pb)

和

(Pc, Pd)

限定，找到

p

和

q

（在

[0,1]

范围内），使函数最小化

f(p, q) = D(Px, Pa) + D(Py, Pd) + k D(Px, Py) where 
                                2 <= k <= 5, 
                                Px = p Pa + (1-p) Pb, 
                                Py = q Pc + (1-q) Pd and 
 D(x, y) is the euclidean distance between points x and y

（实际上，Px和Py是线段上的点，并且该函数通过成本为欧倍德距离的k倍的连接链路编码从Pa到Pd的成本） 关于此功能的一些观察： 平行线段总是会导致

p

和

q

中的至少一个为0或1 相交线段总是会导致

p

和

q

定位线段的交点（可以应用三角不等式来证明这一点） 问题： 在线条倾斜且可能分离的一般情况下，我们如何最小化此功能？