Оптимизация двухпараметрической функции расстояния на линейных сегментах (ACM ICPC Regionals Elim.)

Эта проблема является подзадачей задачи, поставленной в отборочном раунде ACM ICPC Kanpur Regionals:

Имея 2 отрезка, ограниченных двумерными точками (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 являются точками на отрезках прямой, и функция кодирует стоимость перехода из Pa в Pd через соединительное звено, стоимость которого в k раз превышает евклидово расстояние)

Некоторые замечания относительно этой функции:

1. Параллельные отрезки всегда будут приводить к тому, что хотя бы один из p и q будет либо 0, либо 1.
2. Пересечение отрезков прямой всегда приводит к тому, что p и q находят точку пересечения отрезков прямой (чтобы доказать это, можно применить неравенство треугольника)

Вопрос: в общем случае, когда линии наклонены и потенциально разделены, как минимизировать эту функцию?